www.wikidata.uk-ua.nina.az

Рекурсивні функції клас функцій введений як уточнення класу обчислюваних функцій В математиці загальноприйнятою є теза п

Рекурсивні функції

Рекурсивні функції — клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій. У зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу, в математичній логіці, основах математики та кібернетиці, як ефективно обчислювані функції. Тільки такі функції можна обчислювати на електронних обчислювальних машинах та інших цифрових пристроях.

При введенні класу ефективно обчислюваних функцій природним чином виникає питання уточнення конструктивних об'єктів, на яких визначено ці функції. Клас всіх таких об'єктів широкий. В той же час, з допомогою методу арифметизації, запропонованого австрійським математиком Куртом Геделем, всі такі об'єкти легко зводяться до натуральних чисел. Тому рекурсивні функції було введено як функції, що визначені на множині натуральних чисел і набувають значення з тієї ж множини натуральних чисел. Перенесення понять і методів вироблених в теорії рекурсивних функцій на функції визначені на складніших конструктивних областях (множини слів деякого алфавіту, формул деякої теорії, графів тощо) не створює принципових ускладнень.

Далі, під словом «функція» слід розуміти функцію, визначену на множині натуральних чисел зі значеннями із множини натуральних чисел.
В теорії алгоритмів під словом рекурсивна функція мають на увазі тотальну частково рекурсивну функцію, тобто вужче поняття ніж в цій статті. Якщо вас вчили поняттю ЧРФ - вважайте що далі під терміном "рекурсивна функція" мають на увазі частково рекурсивну. Хоча це все треба уточнити з посиланням на АД

Поняття рекурсивних функцій Редагувати

Базовими примітивними функціями, за визначенням, є:

  1. нульова функція
  2. функція наступності
  3. функція проектування

Операція суперпозиції Редагувати

Кажуть, що функція виникає із функцій , , …, суперпозицією, якщо

Операція примітивної рекурсії Редагувати

Функція утворюється із функцій за допомогою примітивної рекурсії, якщо для всіх натуральних значень маємо

Операція мінімізації Редагувати

Позначимо через найменше значення , для якого . Будемо вважати, що не визначено, якщо:

  1. значення визначено для всіх , але відмінні від , а значення не визначено (α = 0, 1, 2, …) або
  2. значення визначені для всіх α = 0, 1, 2, … та відмінні від .

Таким чином, значення є функцією від змінних . Кажуть, що ця функція отримана від функції із допомогою мінімізації.

Примітивно рекурсивна функція Редагувати

Функція називається примітивно рекурсивною, якщо її можна отримати із функцій , та скінченною кількістю операцій суперпозиції та примітивної рекурсії.

Частково рекурсивна функція Редагувати

Функція називається частково рекурсивною, якщо отримана із вказаних функцій застосуванням скінченної кількості операцій суперпозиції, примітивної рекурсії та мінімізації. Всюди визначена частково рекурсивна функція називається загальнорекурсивною.

Одним з популярних прикладів загальнорекурсивної, але не примітивно рекурсивної функції є функція Акермана.

Дослідження рекурсивних функцій Редагувати

Рекурсивні функції, виступаючи як еквівалент поняття ефективно рекурсивних функцій з моменту їх введення піддавались інтенсивному дослідженню.

Перш за все, в класі рекурсивних функцій були виділені та вивчені підкласи простіших функцій — примітивно рекурсивних, елементарних за Л. Кальмару. Доведено, що клас загальнорекурсивних функцій ширший класу примітивно рекурсивний: існують загальнорекурсивні функції, що не є примітивно рекурсивними. Очевидно, що клас частково ширший класу загальнорекурсивних функцій.

Доведено, також, що будь-яка частково рекурсивна функція може бути представлена у вигляді:

Де і  — примітивно рекурсивні функції, тобто, для отримання будь-якої частково рекурсивної функції оператор μ можна застосувати не більше одного разу.

Робились спроби класифікації рекурсивних функцій. Класифікацію примітивно рекурсивних функцій здійснив польський математик А. Гжегорчик, а класифікацію, основану на понятті звідності (в теорії алгоритмів), виконав американський математик Е. Пост.

Алгебри рекурсивних функцій Редагувати

Також досліджувались алгебри рекурсивних функцій: на множині рекурсивних функцій визначались ті чи інші операції, відносно яких множини функцій утворювали універсальні алгебри. Як такі операції обирались операції суперпозиції (*), додавання (+) а також операція обернення визначена схемою , та операція ітерації i, що визначається схемою , . Нехай ,

де функція [α] означає максимальне ціле число, не більше за α.

Доведено, що всі одномісні примітивно рекурсивні функції, і лише вони можуть бути отримані із функцій , скінченною кількістю операцій додавання, суперпозиції та ітерації.

Аналогічно, кожну загальнорекурсивну функцію можна отримати із функцій , скінченною кількістю операцій додавання суперпозиції та обернення, при чому останню виконують лише тоді, коли її результатом є всюди визначена функція. Якщо зняти це обмеження, тоді можна отримати всі одномісні частково рекурсивні функції.

Головним чином, досліджувались три алгебри:

де , та  — множини всіх одномісних примітивно рекурсивних, частково рекурсивних та загальнорекурсивних функцій. Досліджувались найприродніші питання: наявність скінченних базисів, приклади підалгебр, описання максимальних підалгебр, тобто, таких підалгебр, які не містяться в жодних інших підалгебрах самих алгебр, ізоморфізми та автоморфізми підалгебр, конгруенції на підалгебрах, питання скінченної визначеності алгебри тощо.

Разом із дослідженням рекурсивних функцій, широко досліджуються рекурсивні предикати і пов'язані з ними множини — підмножини множини натуральних чисел.

Рекурсивні функції в програмуванні Редагувати

Базисний приклад в мові PHP: При створенні нової функції f() в її тілі викликається та сама функція f() зі зміненим аргументом: 

function f($x){ # Обчислення та друк добутку числа на 2. return $x*2; $y=$x*2; # Виклик функції f() в власному тілі ще раз, але з новим аргументом. f($y); } # Приклад 1: Отримуємо числа добуток 1*2 яких ще раз перемножувався на 2: # 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 і т.д. print f(1); # Приклад 2: Отримуємо числа добуток 3*2 яких ще раз перемножувався на 3: # 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144 і т.д. print f(3);

Див. також Редагувати

Примітки Редагувати

  1. Зустрічається і менш точний термін функція слідування

Джерела Редагувати


Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Rekursivni funkciyi klas funkcij vvedenij yak utochnennya klasu obchislyuvanih funkcij V matematici zagalnoprijnyatoyu ye teza pro te sho klas funkcij dlya obchislennya yakih isnuyut algoritmi pri najshirshomu rozuminni algoritmu zbigayetsya z klasom rekursivnih funkcij U zv yazku z cim rekursivni funkciyi grayut vazhlivu rol v matematici ta yiyi zastosuvannyah v pershu chergu v matematichnij logici osnovah matematiki ta kibernetici yak efektivno obchislyuvani funkciyi Tilki taki funkciyi mozhna obchislyuvati na elektronnih obchislyuvalnih mashinah ta inshih cifrovih pristroyah Pri vvedenni klasu efektivno obchislyuvanih funkcij prirodnim chinom vinikaye pitannya utochnennya konstruktivnih ob yektiv na yakih viznacheno ci funkciyi Klas vsih takih ob yektiv shirokij V toj zhe chas z dopomogoyu metodu arifmetizaciyi zaproponovanogo avstrijskim matematikom Kurtom Gedelem vsi taki ob yekti legko zvodyatsya do naturalnih chisel Tomu rekursivni funkciyi bulo vvedeno yak funkciyi sho viznacheni na mnozhini naturalnih chisel i nabuvayut znachennya z tiyeyi zh mnozhini naturalnih chisel Perenesennya ponyat i metodiv viroblenih v teoriyi rekursivnih funkcij na funkciyi viznacheni na skladnishih konstruktivnih oblastyah mnozhini sliv deyakogo alfavitu formul deyakoyi teoriyi grafiv tosho ne stvoryuye principovih uskladnen Dali pid slovom funkciya slid rozumiti funkciyu viznachenu na mnozhini naturalnih chisel zi znachennyami iz mnozhini naturalnih chisel V teoriyi algoritmiv pid slovom rekursivna funkciya mayut na uvazi totalnu chastkovo rekursivnu funkciyu tobto vuzhche ponyattya nizh v cij statti Yaksho vas vchili ponyattyu ChRF vvazhajte sho dali pid terminom rekursivna funkciya mayut na uvazi chastkovo rekursivnu Hocha ce vse treba utochniti z posilannyam na ADZmist 1 Ponyattya rekursivnih funkcij 1 1 Operaciya superpoziciyi 1 2 Operaciya primitivnoyi rekursiyi 1 3 Operaciya minimizaciyi 1 4 Primitivno rekursivna funkciya 1 5 Chastkovo rekursivna funkciya 2 Doslidzhennya rekursivnih funkcij 2 1 Algebri rekursivnih funkcij 3 Rekursivni funkciyi v programuvanni 4 Div takozh 5 Primitki 6 DzherelaPonyattya rekursivnih funkcij RedaguvatiBazovimi primitivnimi funkciyami za viznachennyam ye nulova funkciya O n x 1 x n 0 displaystyle O n x 1 dots x n 0 nbsp funkciya nastupnosti 1 s x x 1 displaystyle s x x 1 nbsp funkciya proektuvannya I m n x 1 x n x m displaystyle I m n x 1 dots x n x m nbsp Operaciya superpoziciyi Redaguvati Kazhut sho funkciya g x 1 x m displaystyle g x 1 dots x m nbsp vinikaye iz funkcij f x 1 x n displaystyle f x 1 dots x n nbsp f 1 x 1 x m displaystyle f 1 x 1 dots x m nbsp f n x 1 x m displaystyle f n x 1 dots x m nbsp superpoziciyeyu yaksho g x 1 x m f f 1 x 1 x m f n x 1 x m displaystyle g x 1 dots x m f Big f 1 x 1 dots x m dots f n x 1 dots x m Big nbsp Operaciya primitivnoyi rekursiyi Redaguvati Dokladnishe Operaciya primitivnoyi rekursiyiFunkciya f x 1 x n 1 displaystyle f x 1 dots x n 1 nbsp utvoryuyetsya iz funkcij g x 1 x n h x 1 x n 2 displaystyle g x 1 dots x n h x 1 dots x n 2 nbsp za dopomogoyu primitivnoyi rekursiyi yaksho dlya vsih naturalnih znachen x 1 x n y displaystyle x 1 dots x n y nbsp mayemo f x 1 x n 0 g x 1 x n displaystyle f x 1 dots x n 0 g x 1 dots x n nbsp f x 1 x n y 1 h x 1 x n y f x 1 x n y displaystyle f x 1 dots x n y 1 h Big x 1 dots x n y f x 1 dots x n y Big nbsp Operaciya minimizaciyi Redaguvati Dokladnishe Operaciya minimizaciyiPoznachimo cherez m y f x 1 x n 1 y x n displaystyle mu y f x 1 dots x n 1 y x n nbsp najmenshe znachennya a displaystyle alpha nbsp dlya yakogo f x 1 x n 1 a x n displaystyle f x 1 dots x n 1 alpha x n nbsp Budemo vvazhati sho m y f x 1 x n 1 y x n displaystyle mu y f x 1 dots x n 1 y x n nbsp ne viznacheno yaksho znachennya f x 1 x n 1 a displaystyle f x 1 dots x n 1 alpha nbsp viznacheno dlya vsih y lt a displaystyle y lt alpha nbsp ale vidminni vid x n displaystyle x n nbsp a znachennya f x 1 x n 1 a displaystyle f x 1 dots x n 1 alpha nbsp ne viznacheno a 0 1 2 abo znachennya f x 1 x n 1 a displaystyle f x 1 dots x n 1 alpha nbsp viznacheni dlya vsih a 0 1 2 ta vidminni vid x n displaystyle x n nbsp Takim chinom znachennya m y f x 1 x n 1 y x n displaystyle mu y f x 1 dots x n 1 y x n nbsp ye funkciyeyu g x 1 x n displaystyle g x 1 dots x n nbsp vid zminnih x 1 x n displaystyle x 1 dots x n nbsp Kazhut sho cya funkciya otrimana vid funkciyi f x 1 x n 1 y displaystyle f x 1 dots x n 1 y nbsp iz dopomogoyu minimizaciyi Primitivno rekursivna funkciya Redaguvati Funkciya nazivayetsya primitivno rekursivnoyu yaksho yiyi mozhna otrimati iz funkcij s x displaystyle s x nbsp O n x 1 x n displaystyle O n x 1 dots x n nbsp ta I m n x 1 x n displaystyle I m n x 1 dots x n nbsp skinchennoyu kilkistyu operacij superpoziciyi ta primitivnoyi rekursiyi Chastkovo rekursivna funkciya Redaguvati Funkciya nazivayetsya chastkovo rekursivnoyu yaksho otrimana iz vkazanih funkcij zastosuvannyam skinchennoyi kilkosti operacij superpoziciyi primitivnoyi rekursiyi ta minimizaciyi Vsyudi viznachena chastkovo rekursivna funkciya nazivayetsya zagalnorekursivnoyu Odnim z populyarnih prikladiv zagalnorekursivnoyi ale ne primitivno rekursivnoyi funkciyi ye funkciya Akermana Doslidzhennya rekursivnih funkcij RedaguvatiRekursivni funkciyi vistupayuchi yak ekvivalent ponyattya efektivno rekursivnih funkcij z momentu yih vvedennya piddavalis intensivnomu doslidzhennyu Persh za vse v klasi rekursivnih funkcij buli vidileni ta vivcheni pidklasi prostishih funkcij primitivno rekursivnih elementarnih za L Kalmaru Dovedeno sho klas zagalnorekursivnih funkcij shirshij klasu primitivno rekursivnij isnuyut zagalnorekursivni funkciyi sho ne ye primitivno rekursivnimi Ochevidno sho klas chastkovo shirshij klasu zagalnorekursivnih funkcij Dovedeno takozh sho bud yaka chastkovo rekursivna funkciya mozhe buti predstavlena u viglyadi g x 1 x s ϕ m z f x 1 x s z 0 displaystyle g x 1 dots x s phi mu z f x 1 dots x s z 0 nbsp De ϕ displaystyle phi nbsp i f displaystyle f nbsp primitivno rekursivni funkciyi tobto dlya otrimannya bud yakoyi chastkovo rekursivnoyi funkciyi operator m mozhna zastosuvati ne bilshe odnogo razu Robilis sprobi klasifikaciyi rekursivnih funkcij Klasifikaciyu primitivno rekursivnih funkcij zdijsniv polskij matematik A Gzhegorchik a klasifikaciyu osnovanu na ponyatti zvidnosti v teoriyi algoritmiv vikonav amerikanskij matematik E Post Algebri rekursivnih funkcij Redaguvati Takozh doslidzhuvalis algebri rekursivnih funkcij na mnozhini rekursivnih funkcij viznachalis ti chi inshi operaciyi vidnosno yakih mnozhini funkcij utvoryuvali universalni algebri Yak taki operaciyi obiralis operaciyi superpoziciyi dodavannya a takozh operaciya obernennya f 1 displaystyle f 1 nbsp viznachena shemoyu f 1 x m y f y x displaystyle f 1 x mu y f y x nbsp ta operaciya iteraciyi i sho viznachayetsya shemoyu g 0 0 displaystyle g 0 0 nbsp g x 1 f g x displaystyle g x 1 f g x nbsp Nehaj s x x 1 displaystyle s x x 1 nbsp g x x x 2 0 displaystyle g x begin cases x sqrt x 2 0 end cases nbsp yaksho x gt x 2 displaystyle x gt sqrt x 2 nbsp inakshede funkciya a oznachaye maksimalne cile chislo ne bilshe za a Dovedeno sho vsi odnomisni primitivno rekursivni funkciyi i lishe voni mozhut buti otrimani iz funkcij s x displaystyle s x nbsp g x displaystyle g x nbsp skinchennoyu kilkistyu operacij dodavannya superpoziciyi ta iteraciyi Analogichno kozhnu zagalnorekursivnu funkciyu mozhna otrimati iz funkcij s x displaystyle s x nbsp g x displaystyle g x nbsp skinchennoyu kilkistyu operacij dodavannya superpoziciyi ta obernennya pri chomu ostannyu vikonuyut lishe todi koli yiyi rezultatom ye vsyudi viznachena funkciya Yaksho znyati ce obmezhennya todi mozhna otrimati vsi odnomisni chastkovo rekursivni funkciyi Golovnim chinom doslidzhuvalis tri algebri A p r F p r i displaystyle mathfrak A pr langle F pr i rangle nbsp A c r F c r 1 displaystyle mathfrak A cr langle F cr 1 rangle nbsp A g r F g r 1 displaystyle mathfrak A gr langle F gr 1 rangle nbsp de F p r displaystyle F pr nbsp F c r displaystyle F cr nbsp ta F g r displaystyle F gr nbsp mnozhini vsih odnomisnih primitivno rekursivnih chastkovo rekursivnih ta zagalnorekursivnih funkcij Doslidzhuvalis najprirodnishi pitannya nayavnist skinchennih bazisiv prikladi pidalgebr opisannya maksimalnih pidalgebr tobto takih pidalgebr yaki ne mistyatsya v zhodnih inshih pidalgebrah samih algebr izomorfizmi ta avtomorfizmi pidalgebr kongruenciyi na pidalgebrah pitannya skinchennoyi viznachenosti algebri tosho Razom iz doslidzhennyam rekursivnih funkcij shiroko doslidzhuyutsya rekursivni predikati i pov yazani z nimi mnozhini pidmnozhini mnozhini naturalnih chisel Rekursivni funkciyi v programuvanni RedaguvatiBazisnij priklad v movi PHP Pri stvorenni novoyi funkciyi f v yiyi tili viklikayetsya ta sama funkciya f zi zminenim argumentom function f x Obchislennya ta druk dobutku chisla na 2 return x 2 y x 2 Viklik funkciyi f v vlasnomu tili she raz ale z novim argumentom f y Priklad 1 Otrimuyemo chisla dobutok 1 2 yakih she raz peremnozhuvavsya na 2 2 4 8 16 32 64 128 256 512 1024 2048 i t d print f 1 Priklad 2 Otrimuyemo chisla dobutok 3 2 yakih she raz peremnozhuvavsya na 3 6 12 24 48 96 192 384 768 1536 3072 6144 i t d print f 3 Div takozh RedaguvatiTeza Chercha Rekursiya Teoriya obchislyuvanosti Universalni rekursivni funkciyiPrimitki Redaguvati Zustrichayetsya i mensh tochnij termin funkciya sliduvannyaDzherela RedaguvatiEnciklopediya kibernetiki u 2 t za red V M Glushkova Kiyiv Gol red Ukrayinskoyi radyanskoyi enciklopediyi 1973 T 2 S 290 292 Rodzhers H Teoriya rekursivnyh funkcij i effektivnaya vychislimost M Mir 1972 416 s ros nbsp Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Rekursivni funkciyi amp oldid 39227283 Chastkovo rekursivna funkciya