Funcția Gödel

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 9 ianuarie 2021; verificările necesită 3 modificări .

Funcția Gödel este o funcție folosită în teoria algoritmilor pentru a facilita enumerarea mulțimilor de numere naturale.

Definiție

Funcția Gödel este expresia [1] : $\Gamma (x,y)$

\Gamma (x,y)=rest(l(x),1+(y+1)r(x))

, Unde

$l(n),r(n)$ sunt membrii din stânga și din dreapta perechii cu numărul enumerarii Cantor de numere naturale , este restul după împărțirea la . $n$ $rest(x,y)$ $X$ $y$

Proprietăți

Funcția Gödel este primitiv recursivă .
Oricare ar fi șirul finit de numere naturale , sistemul de ecuații $a_{0},a_{1},...,a_{n)$

${\displaystyle \Gamma (x,0)=a_{0},\Gamma (x,1)=a_{1},...,\Gamma (x,n)=a_{n))$ are cel puțin o soluție [2] .

Note

↑ Algoritmi și funcții recursive, 1986 , p. 62.
↑ Algoritmi și funcții recursive, 1986 , p. 62-64.

Literatură

Algoritmi Maltsev AI și funcții recursive. — M .: Nauka, 1986. — 367 p. — 10.400 de exemplare.