Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

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

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

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

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

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

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

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

Операція суперпозиції

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

image

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

Докладніше: Операція примітивної рекурсії

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

image
image

Операція мінімізації

Докладніше: Операція мінімізації

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

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

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

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

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

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

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

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

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

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

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

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

image,

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

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

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

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

image якщо image
інакше

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

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

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

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

  • image
  • image
  • image

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

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

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

Базисний приклад в мові 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. Зустрічається і менш точний термін функція слідування

Література


image Це незавершена стаття з математики.
Ви можете проєкту, виправивши або дописавши її.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Дата публікації:
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 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 ADPonyattya rekursivnih funkcijBazovimi primitivnimi funkciyami za viznachennyam ye nulova funkciya O n x 1 x n 0 displaystyle O n x 1 dots x n 0 funkciya nastupnosti s x x 1 displaystyle s x x 1 funkciya proektuvannya I m n x 1 x n x m displaystyle I m n x 1 dots x n x m Operaciya superpoziciyi Kazhut sho funkciya g x 1 x m displaystyle g x 1 dots x m vinikaye iz funkcij f x 1 x n displaystyle f x 1 dots x n f 1 x 1 x m displaystyle f 1 x 1 dots x m f n x 1 x m displaystyle f n x 1 dots x m 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 Operaciya primitivnoyi rekursiyi Dokladnishe Operaciya primitivnoyi rekursiyi Funkciya f x 1 x n 1 displaystyle f x 1 dots x n 1 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 za dopomogoyu primitivnoyi rekursiyi yaksho dlya vsih naturalnih znachen x 1 x n y displaystyle x 1 dots x n y 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 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 Operaciya minimizaciyi Dokladnishe Operaciya minimizaciyi Poznachimo 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 najmenshe znachennya a displaystyle alpha dlya yakogo f x 1 x n 1 a x n displaystyle f x 1 dots x n 1 alpha x n 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 ne viznacheno yaksho znachennya f x 1 x n 1 a displaystyle f x 1 dots x n 1 alpha viznacheno dlya vsih y lt a displaystyle y lt alpha ale vidminni vid x n displaystyle x n a znachennya f x 1 x n 1 a displaystyle f x 1 dots x n 1 alpha ne viznacheno a 0 1 2 abo znachennya f x 1 x n 1 a displaystyle f x 1 dots x n 1 alpha viznacheni dlya vsih a 0 1 2 ta vidminni vid x n displaystyle x n 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 ye funkciyeyu g x 1 x n displaystyle g x 1 dots x n vid zminnih x 1 x n displaystyle x 1 dots x n Kazhut sho cya funkciya otrimana vid funkciyi f x 1 x n 1 y displaystyle f x 1 dots x n 1 y iz dopomogoyu minimizaciyi Primitivno rekursivna funkciya Funkciya nazivayetsya primitivno rekursivnoyu yaksho yiyi mozhna otrimati iz funkcij s x displaystyle s x O n x 1 x n displaystyle O n x 1 dots x n ta I m n x 1 x n displaystyle I m n x 1 dots x n skinchennoyu kilkistyu operacij superpoziciyi ta primitivnoyi rekursiyi Chastkovo rekursivna funkciya 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 funkcijRekursivni 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 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 De ϕ displaystyle phi i f displaystyle f 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 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 viznachena shemoyu f 1 x m y f y x displaystyle f 1 x mu y f y x ta operaciya iteraciyi i sho viznachayetsya shemoyu g 0 0 displaystyle g 0 0 g x 1 f g x displaystyle g x 1 f g x Nehaj s x x 1 displaystyle s x x 1 g x x x 2 0 displaystyle g x begin cases x sqrt x 2 0 end cases yaksho x gt x 2 displaystyle x gt sqrt x 2 inakshe de 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 g x displaystyle g x skinchennoyu kilkistyu operacij dodavannya superpoziciyi ta iteraciyi Analogichno kozhnu zagalnorekursivnu funkciyu mozhna otrimati iz funkcij s x displaystyle s x g x displaystyle g x 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 A c r F c r 1 displaystyle mathfrak A cr langle F cr 1 rangle A g r F g r 1 displaystyle mathfrak A gr langle F gr 1 rangle de F p r displaystyle F pr F c r displaystyle F cr ta F g r displaystyle F gr 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 programuvanniBazisnij 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 takozhTeza Chercha Rekursiya Teoriya obchislyuvanosti Universalni rekursivni funkciyiPrimitkiZustrichayetsya i mensh tochnij termin funkciya sliduvannyaLiteratura ukr Formalni movi ta algoritmichni modeli I F Golinej 2023 180 s Enciklopediya kibernetiki u 2 t za red V M Glushkova Kiyiv Gol red Ukrayinskoyi radyanskoyi enciklopediyi 1973 T 2 S 290 292 Teoriya rekursivnyh funkcij i effektivnaya vychislimost M Mir 1972 416 s ros Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi
Топ