Självtillämpbarhet

Självtillämpbarhet i teorin om algoritmer är egenskapen hos en algoritm för att framgångsrikt slutföra data som är en formell registrering av samma algoritm.

Problemet med självtillämpningsigenkänning är algoritmiskt olösligt och går ut på att hitta en algoritm som gör det möjligt att i ett ändligt antal steg i den formella notationen av någon algoritm ta reda på om den är självtillämpbar eller inte. Även om detta problem är något konstlat och inte av självständigt intresse, används det ofta för att bevisa olösligheten hos andra, mer komplexa problem. Den generella metoden för sådana slutsatser är att från antagandet om existensen av en algoritm som löser ett visst problem, härleds förekomsten av en algoritm som löser problemet med självtillämpningsigenkänning.

Bevis på algoritmisk obestämbarhet

Bevis genom motsägelse . Antag att det finns en algoritm som känner igen självtillämpbarhet. Baserat på Turing-uppsatsen finns det även en Turing-maskin som implementerar denna algoritm. Låt oss beteckna en sådan maskin som . På dess band skrivs ett kodat program från en annan Turing-maskin in på något sätt, och efter arbetet bearbetas den inmatade datan till ett ord om det ursprungliga programmet var självtillämpligt, eller till ett ord om det inte var självtillämpligt. $A$ $y$ $n$

I det andra steget modifierar vi maskinen något så att den fortfarande bearbetar icke-självtillämpbara program i , och loopar på självtillämpliga program , det vill säga att den inte är tillämplig på dem. Det är väldigt lätt att göra en sådan omvandling - efter att ha skrivit ett ord avslutar maskinen inte sitt arbete, utan fortsätter att i oändlighet skriva det till bandet. Låt oss beteckna den här bilen som . Förekomsten av en sådan maskin leder till en motsägelse, eftersom den inte kan vara vare sig självtillämplig eller icke-självtillämplig. I själva verket, om det är självtillämpligt, så är det tillämpligt på sin egen notation. Men enligt maskinens konstruktion indikerar detta bara att den inte är självanvändbar. Om den inte är självtillämplig är den tillämplig på sin egen konstruktion, eftersom den är tillämplig på vilken som helst registrering av en icke-självtillämplig maskin. Men detta betyder bara att det är självtillämpligt. Utgående från detta dras en slutsats om omöjligheten att bygga en maskin , eftersom det då skulle vara lätt att komma från den . $A$ $n$ $y$ $A_{1}$ $A_{1}$ $A_{1}$ $A_{1}$ $A_{1}$ $A_{1}$ $A_{1}$ $A$ $A_{1}$

Litteratur

V. I. IGOSHIN Matematisk logik och teori för algoritmer. - M . : Academy, 2004. - S. 369-370. — 448 sid. - 5100 exemplar. — ISBN 5-7695-1363-2 .
A. L. Semyonov. Självanvändande program // Texters matematik . - 2002. - 16 sid. - 3000 exemplar. — ISBN 5-94057-006-2 .
E. M. Ivanov. Gödels argument // Om problemet med "beräknebarhet" av medvetandets funktion .
Michiel Hazewinkel. Undecidability // Encyclopaedia of Mathematics . - Berlin: Springer Netherland, 2002. - ISBN 1-4020-0609-8 . (Engelsk)
Arto Salomaa. 4.3 Rekursionssats och grundläggande obestämbarhetsresultat // Beräkning och automater . - Cambridge University Press, 1985. - V. 25. - S. 90. - 284 sid. — ISBN 9780521302456 . (Engelsk)

Se även

Sluta problem