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

Література

  • (укр.) Формальні мови та алгоритмічні моделі. — І.-Ф.  : Голіней, 2023. — 180 с.
  • Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973. — Т. 2. — С. 290–292.
  • (інші мови). Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
  • Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)


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

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

Zagalni rekursivni funkciyi chastkovi rekursivni funkciyi m rekursivni funkciyi v matematici ce chastkovi funkciyi z naturalnih chisel v naturalni chisla vvedeni yak utochnennya klasu obchislennih funkcij 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 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 ViznachennyaBazovimi primitivnimi funkciyami za viznachennyam ye nulova funkciya On x1 xn 0 displaystyle O n x 1 dots x n 0 funkciya nastupnosti s x x 1 displaystyle s x x 1 funkciya proektuvannya Imn x1 xn xm displaystyle I m n x 1 dots x n x m Operaciya superpoziciyi Dokladnishe Kompoziciya funkcij Kazhut sho funkciya g x1 xm displaystyle g x 1 dots x m vinikaye iz funkcij f x1 xn displaystyle f x 1 dots x n f1 x1 xm displaystyle f 1 x 1 dots x m fn x1 xm displaystyle f n x 1 dots x m superpoziciyeyu yaksho g x1 xm f f1 x1 xm fn x1 xm 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 x1 xn 1 displaystyle f x 1 dots x n 1 utvoryuyetsya iz funkcij g x1 xn h x1 xn 2 displaystyle g x 1 dots x n h x 1 dots x n 2 za dopomogoyu primitivnoyi rekursiyi yaksho dlya vsih naturalnih znachen x1 xn y displaystyle x 1 dots x n y mayemo f x1 xn 0 g x1 xn displaystyle f x 1 dots x n 0 g x 1 dots x n f x1 xn y 1 h x1 xn y f x1 xn 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 my f x1 xn 1 y xn displaystyle mu y f x 1 dots x n 1 y x n najmenshe znachennya a displaystyle alpha dlya yakogo f x1 xn 1 a xn displaystyle f x 1 dots x n 1 alpha x n Budemo vvazhati sho my f x1 xn 1 y xn displaystyle mu y f x 1 dots x n 1 y x n ne viznacheno yaksho znachennya f x1 xn 1 a displaystyle f x 1 dots x n 1 alpha viznacheno dlya vsih y lt a displaystyle y lt alpha ale vidminni vid xn displaystyle x n a znachennya f x1 xn 1 a displaystyle f x 1 dots x n 1 alpha ne viznacheno a 0 1 2 abo znachennya f x1 xn 1 a displaystyle f x 1 dots x n 1 alpha viznacheni dlya vsih a 0 1 2 ta vidminni vid xn displaystyle x n Takim chinom znachennya my f x1 xn 1 y xn displaystyle mu y f x 1 dots x n 1 y x n ye funkciyeyu g x1 xn displaystyle g x 1 dots x n vid zminnih x1 xn displaystyle x 1 dots x n Kazhut sho cya funkciya otrimana vid funkciyi f x1 xn 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 On x1 xn displaystyle O n x 1 dots x n ta Imn x1 xn 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 x1 xs ϕ mz f x1 xs 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 Iyerarhiya Gzhegorchika primitivno rekursivnih funkcij polskogo matematika A Gzhegorchika 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 my 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 Apr Fpr i displaystyle mathfrak A pr langle F pr i rangle Acr Fcr 1 displaystyle mathfrak A cr langle F cr 1 rangle Agr Fgr 1 displaystyle mathfrak A gr langle F gr 1 rangle de Fpr displaystyle F pr Fcr displaystyle F cr ta Fgr 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 inshi movi Teoriya rekursivnyh funkcij i effektivnaya vychislimost M Mir 1972 416 s ros Hopcroft John E Ullman Jeffrey D 2001 Vstup do teoriyi avtomativ mov i obchislen vid 2nd Addison Wesley s 521 angl Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi

Дата публікації:
Топ