Gödel-toiminto

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. tammikuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Gödel -funktio on algoritmien teoriassa käytetty funktio, joka helpottaa luonnollisten lukujoukkojen laskemista.

Määritelmä

Gödel-funktio on lauseke [1] : ${\näyttötyyli \Gamma (x,y)}$

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

, missä

${\näyttötyyli l(n),r(n)}$ ovat parin vasen ja oikea jäsenet luonnollisten lukujen Cantor-laskelman numerolla , on jakojäännös luvulla jakamisen jälkeen . $n$ $rest(x,y)$ $x$ $y$

Ominaisuudet

Gödel-funktio on primitiivisesti rekursiivinen .
Mikä tahansa luonnollisten lukujen rajallinen sarja tahansa , yhtälöjärjestelmä ${\displaystyle a_{0},a_{1},...,a_{n))$

${\displaystyle \Gamma (x,0)=a_{0},\Gamma (x,1)=a_{1},...,\Gamma (x,n)=a_{n))$ on vähintään yksi ratkaisu [2] .

Muistiinpanot

↑ Algoritmit ja rekursiiviset funktiot, 1986 , s. 62.
↑ Algoritmit ja rekursiiviset funktiot, 1986 , s. 62-64.

Kirjallisuus

Maltsev AI Algoritmit ja rekursiiviset funktiot. - M .: Nauka, 1986. - 367 s. — 10 400 kappaletta.