Rekurzivní funkce (teorie vyčíslitelnosti)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 4. června 2021; kontroly vyžadují 2 úpravy .

Termín rekurzivní funkce v teorii vyčíslitelnosti se používá k označení tří tříd funkcí:

primitivní rekurzivní funkce ;
obecné rekurzivní funkce ;
částečně rekurzivní funkce .

Ten se shoduje s třídou Turingově vyčíslitelných funkcí . Definice těchto tří tříd spolu úzce souvisí. Zavedl je Kurt Gödel , aby formalizoval pojem vyčíslitelnosti.

Sada částečně rekurzivních funkcí zahrnuje množinu obecných rekurzivních funkcí a obecné rekurzivní funkce zahrnují primitivní rekurzivní funkce. Částečně rekurzivní funkce se někdy označují jednoduše jako rekurzivní funkce.

Primitivní rekurzivní funkce

Definice

Definice pojmu primitivní rekurzivní funkce je induktivní . Skládá se ze specifikace třídy základních primitivních rekurzivních funkcí a dvou operátorů ( superpozice a primitivní rekurze ), které umožňují vytvářet nové primitivní rekurzivní funkce založené na těch stávajících.

Mezi základní primitivní rekurzivní funkce patří následující tři typy funkcí:

Nulová funkce je funkce bez argumentů, která vždy vrací 0 . $Ó$
Funkce posloupnosti s jednou proměnnou, která přiřadí libovolnému přirozenému číslu bezprostředně následující přirozené číslo . Například . $S$ $X$ $x+1$ $S(41)=42$
Funkce , kde , z n proměnných, které přiřazují libovolné uspořádané množině přirozených čísel číslo z této množiny. Například . $I_{n}^{m}$ $0<m\leqslant n$ $x_{1},\tečky ,x_{n}$ $x_{m}$ $I_{3}^{2}(10,20,30)=20$

Operátory substituce a primitivní rekurze jsou definovány takto:

Operátor superpozice (někdy substituční operátor ). Nechť je funkcí m proměnných a je uspořádaná množina funkcí proměnných. Pak výsledkem superpozice funkcí do funkce je funkce proměnných , která libovolné uspořádané množině přirozených čísel přiřadí číslo $F$ $g_{1},\tečky ,g_{m}$ $n$ $g_{k}$ $F$ $h$ $n$ $x_{1},\tečky ,x_{n}$ $h(x_{1},\ldots ,x_{n})=f{\big (}g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m }(x_{1},\ldots ,x_{n}){\big )}.$
Operátor primitivní rekurze . Dovolit být funkcí proměnných a být funkcí proměnných. Pak výsledkem aplikace primitivního rekurzního operátoru na dvojici funkcí je funkce proměnné tvaru $F$ $n$ $G$ $n+2$ $F$ $G$ $h$ $n+1$ $h(x_{1},\ldots ,x_{n},0)=f(x_{1},\ldots ,x_{n});$ $h(x_{1},\ldots ,x_{n},y+1)=g(x_{1},\ldots ,x_{n},y,h(x_{1},\ldots, x_{n},y)).$

V této definici lze proměnnou chápat jako iterační čítač, — jako počáteční funkci na začátku iteračního procesu, která vydává určitou posloupnost funkcí proměnných počínaje , a — jako operátor, který přijímá jako vstupní proměnné , číslo kroku iterace , funkce v daném kroku iterace a funkce návratu v dalším kroku iterace. $y$ $F$ $n$ $F$ $G$ $n$ $x_{1},\ldots ,x_{n}$ $y$ $h(x_{1},\ldots ,x_{n},y)$

Množina primitivních rekurzivních funkcí je minimální množina obsahující všechny základní funkce a uzavřená pod specifikovanými operátory substituce a primitivní rekurze.

Pokud jde o imperativní programování , primitivní rekurzivní funkce odpovídají programovým blokům, které používají pouze aritmetické operace, stejně jako podmíněný operátor a operátor aritmetické smyčky (operátor smyčky, ve kterém je znám počet iterací v době, kdy smyčka začíná). Pokud programátor začne používat operátor smyčky while, u kterého není počet iterací předem znám a v zásadě může být nekonečný, přechází do třídy částečně rekurzivních funkcí.

Příklady

Uveďme řadu známých aritmetických funkcí , které jsou primitivně rekurzivní.

Funkci Sčítání dvou přirozených čísel ( ) lze považovat za primitivní rekurzivní funkci dvou proměnných získanou aplikací primitivního rekurzního operátoru na funkce a , z nichž druhá se získá dosazením hlavní funkce do hlavní funkce : $Součet(a,\;b)=a+b$ $já_{1}^{1}$ $F$ $já_{3}^{3}$ $S$

Součet(x,\;0)=I_{1}^{1}(x)

;

Součet(x,\;y+1)=F(x,\;y,\;Součet(x,\;y))

;

F(x,\;y,\;z)=S(I_{3}^{3}(x,\;y,\;z))

Násobení dvou přirozených čísel ( ) lze považovat za primitivní rekurzivní funkci dvou proměnných, získanou jako výsledek aplikace primitivního rekurzního operátoru na funkce a , z nichž druhý se získá dosazením hlavních funkcí a do sčítání funkce: $Mul(a,\;b)=a\krát b$ $Ó$ $G$ $já_{3}^{1}$ $já_{3}^{3}$

Mul(x,\;0)=O(x)

;

Mul(x,\;y+1)=G(x,\;y,\;Mul(x,y))

;

G(x,\;y,\;z)=Součet(I_{3}^{1}(x,\;y,\;z),I_{3}^{3}(x,\;y, \;z))

Symetrický rozdíl (absolutní hodnota rozdílu) dvou přirozených čísel ( ) lze považovat za primitivní rekurzivní funkci dvou proměnných, získanou aplikací následujících substitucí a primitivních rekurzí: $Sub(a,\;b)=|ab|$

Sub(x,\;y)=Sum(Sub_{1}(x,\;y),\;Sub_{2}(x,\;y))

;

Sub_{2}(x,\;y)=Sub_{1}(I_{2}^{2}(x,\;y),\;I_{2}^{1}(x,\;y) )

;

\left\{{\begin{array}{l}Sub_{1}(x,\;0)=I_{1}^{1}(x)\\Sub_{1}(x,\;y+1 )=f(x,\;y,\;Pod_{1}(x,\;y))\end{pole}}\vpravo.

;

f(x,\;y,\;z)=p(I_{3}^{3}(x,\;y,\;z))

;

\left\{{\begin{array}{l}p(0)=0\\p(y+1)=I_{2}^{1}(y,\;p(y))\end{array }}\že jo.

;

Částečně rekurzivní funkce

Částečně rekurzivní funkce je definována podobně jako primitivní rekurzivní, pouze ke dvěma operátorům, superpozice a primitivní rekurze, je přidán třetí operátor - minimalizace argumentů.

Operátor minimalizace argumentů . Nechť je funkcí n přirozených proměnných. Pak výsledkem použití operátoru minimálního argumentu na funkci je funkce proměnné , daná následující definicí: $F$ $F$ $h$ $n-1$

h(x_{1},\ldots ,x_{n-1})=\min y

, za podmínky

f(x_{1},\ldots ,x_{n-1},\,y)=0

To znamená, že funkce vrací minimální hodnotu posledního argumentu funkce , při které je její hodnota 0.

h

F

Částečně rekurzivní funkce pro některé hodnoty argumentů nemusí být definovány, protože operátor minimalizace argumentů není vždy správně definován, protože funkce nemusí být pro žádné hodnoty argumentu rovna nule. Z hlediska imperativního programování může být výsledkem částečně rekurzivní funkce nejen číslo, ale i výjimka nebo nekonečná smyčka odpovídající nedefinované hodnotě. $F$

Obecná rekurzivní funkce

Obecná rekurzivní funkce je částečně rekurzivní funkce definovaná pro všechny hodnoty argumentů. Problém určení, zda je částečně rekurzivní funkce s daným popisem obecná rekurzivní nebo ne, je algoritmicky nerozhodnutelný .

Vlastnosti

Je snadné pochopit, že jakákoli primitivní rekurzivní funkce je částečně rekurzivní, protože podle definice operátory pro konstrukci částečně rekurzivních funkcí zahrnují operátory pro konstrukci primitivních rekurzivních funkcí.

Je také jasné, že primitivní rekurzivní funkce je definována všude, a proto je obecnou rekurzivní funkcí (primitivní rekurzivní funkce nemá důvod „viset“, protože její konstrukce používá operátory, které definují funkce definované všude).

Je poměrně obtížné dokázat existenci a uvést příklad obecné rekurzivní funkce, která není primitivně rekurzivní. Jedním z populárních příkladů je Ackermannova funkce . Další příklad obecné rekurzivní funkce, která není primitivní rekurzivní, je konstruován Cantorovou diagonální metodou z univerzální funkce pro množinu unárních primitivních rekurzivních funkcí.

Jak ukázal Gödel , částečně rekurzivní funkce se shodují se souborem vypočitatelných funkcí .

Historie jmen

Pojmy „částečně rekurzivní funkce“ a „obecná rekurzivní funkce“ zakořenily z historických důvodů a jsou v podstatě výsledkem nepřesného překladu anglických výrazů částečná rekurzivní funkce a celková rekurzivní funkce , které jsou správněji přeloženy jako „definované rekurzivní funkce. na části množiny možných argumentů“ a „rekurzivní funkce definované na celé množině možných argumentů“. Příslovce „částečně“ neodkazuje na přídavné jméno „rekurzivní“, ale na rozsah funkce. Možná správnější název by byl „částečně definované rekurzivní funkce“ a jednoduše „všude definované rekurzivní funkce“. Dlouhá jména se ale neprosadila.

Viz také

Markovův algoritmus ( produkční programování )
Turingův stroj ( automatické programování )
Postův stroj ( automatické programování )
Lambda kalkul ( funkční programování )
Brainfuck ( imperativní programování )
Unlambda ( funkční kalkul )

Literatura

Hilbert D, Bernays P. Základy matematiky. T. 1. - M.: Nauka, 1979.
Kleene S.K. Úvod do metamatematiky. - M., 1957.
Maltsev AI Algoritmy a rekurzivní funkce. Moskva: Nauka, 1986.
Peter R. Rekurzivní funkce - IL, 1954.
Vereshchagin N. K., Shen A. Lectures on Mathematical Logic and Theory of Algorithms . Část 3. Vyčíslitelné funkce, 2. vydání, revidováno. — M.: MTsNMO, 2002.