Know-how, előadás, rekurzív funkciók
Turing gépek és rekurzív funkciók
Számos különböző technikát vettünk figyelembe primitív rekurzív függvények kialakításában. Mindazonáltal nem világos, hogy milyen messze van ez az osztály. Most megmutatjuk, hogy magában foglalja az összes meglehetősen gyorsan kiszámítható funkciót.
Tétel 75. Minden funkció. amely egy Turing-gépen számítható, nem mint primitív rekurzív (a bemeneti időtartamtól függően), primitív rekurzív.
Emlékezzünk arra, hogy a Turing-gép szavak bemeneteit és kimenetét nullákból, illetve nullákból tekintjük. Mivel a primitív rekurzív függvények érvei és értékei számok, a tételnek csak akkor van értelme, ha elfogadjuk a számok és szavak azonosítását. Amint már említettük, azonosítjuk az n számot az "n + 1" bináris kiterjesztésű nagy rendű bit 1 eltávolítása után kapott szóval.
Amikor a Turing gépek működését szimuláltuk programokkal, négy számban kódoltuk a gép állapotát (a szalag bal oldalán található kódot, a kazetta jobb oldalán lévő kódot, az állapotot és a fej alá tartozó levelet). Ez a kódolás ugyanakkor kényelmes volt. a szalag bal oldala számként számozott a számrendszerben, amelyben az alap egyenlő a gép ábécéjében lévő karakterek számával, és a tér nulla értékű; a szalag jobb oldalával ugyanezt tettük, csak fordított sorrendben (a fej alsó sorrendjében). Ebben az esetben a szimbólum feltüntetése vagy eltávolítása a fejjel egy egyszerű aritmetikai műveletnek felel meg (eltávolítva ezt a részegységet, hozzáadva a számrendszer alapjához és a hozzáadáshoz). Ezzel a kódolással az átmenet funkciók (négy argumentum négy funkciója, amelyek a következő állapotot jelzik az előző függvényeként) egyszerű formulákkal és primitív rekurzívakkal íródnak.
Most vegye fontolóra az iterált átmenet funkciót, amely megmondja, hogy mi lesz a Turing gép állapota t lépések után. Pontosabban négy argumentum négy függvénye van (az első négy argumentum az állapotot kódolja, az ötödik a lépések száma). Definíciójuk a közös rekurzió formája, amelyet csak lebontottunk. Ezért ezek a funkciók primitív rekurzívak. Feltételezzük, hogy a végállapot megjelenése után a gép konfigurációja nem változik. Ha tudjuk, hogy a munkafolyamatok számát egy primitív rekurzív függvény korlátozza. akkor elegendő az ötödik argumentumra (a lépések számára) helyettesíteni annak biztosítására, hogy a végleges gép konfigurációja kezdeti konfigurációjú primitív rekurzív függvény legyen. Következésképpen a munka eredménye a kezdeti adatok primitív rekurzív függvénye.
Ez az érvelés hallgatólagosan felhasználja a különböző funkciók primitív rekurzivitását, amelyek az adatok bemutatásából a másikba való átmenethez kapcsolódnak. Például egy Turing gép bemenete egy bináris szó, melyet egy bizonyos x számmal azonosítottunk. Ez a bemenet megfelel a Turing gép kezdeti konfigurációjának, amelyet négyjegyű számmal kódolunk. Fontos számunkra, hogy ez a négyes függvény primitíven rekurzív módon függ x. Ez könnyen érthető, mert az átalakítás járó átmenet az egyik rendszerből a másikba száma (ugyanazt a szót kódol különböző számok különféle számrendszerek); Az ilyen funkciók primitív rekurzivitása könnyen megállapítható a fent leírt módszerek alkalmazásával. Ezenkívül ki kell vonnunk az eredményt a kimeneti konfigurációból, és vissza kell írni azt is, valamint meg kell kapnunk a hosszt a bemenetből (hogy helyettesítsük a primitív rekurzív függvényt, amely korlátozza a lépések számát). De mindez nem jön ki a fent említett módszerek köréből, és nem fogunk részletesen foglalkozni ezzel.
Ez a tétel meggyőz minket sok meglehetősen nehezen meghatározott funkció primitív rekurzivitására. Például vegye figyelembe az n funkciót (a szám n-edik decimális számjegye). Köztudott, hogy a kiszámított millió ilyen jeleket, így minden okunk megvan azt hinni, hogy bizonyos algoritmusok munka nem volt túl hosszú lenne nagyon furcsa, ha munkájuk során (még a kényelmetlenséget a Turing-gép, programozás) nem állapítható meg, például a funkció cx 2 n elég nagy méretű c. És egy ilyen becslés primitív rekurzív, amely lehetővé teszi számunkra, hogy hivatkozzunk a bizonyított tételre. (Valójában primitív rekurzív függvények vannak, amelyek sokkal gyorsabban nőnek, mint 2 n.)
A primitív rekurzív függvények osztályának másik leírása. a programozók számára érthetőbbek: ezek olyan funkciók, amelyeket egy, az if-then-else-branches és a -cycles-t tartalmazó programban lehet kiszámítani, de nem tartalmaz ciklusokat (és még többet fordul elő és a hurokban lévő for loop paraméter más piszkos változásait) .
87. Állítsa be és igazolja a megfelelő nyilatkozatot.
Részben rekurzív funkciók
A primitív rekurzió és helyettesítés operátorai nem vezetnek bennünket mindenhol meghatározott funkciók osztályától. Ez nem így van a minimizáló operátorral. amiről már említettük. Ez a (k + 1) szabad f függvényre vonatkozik, és k-t ad a g helyi funkciónak. az alábbiak szerint: g (x1. xk) a legkisebb y. amelyre f (x1 .xk, y) = 0.
A kiválasztott szavak jelentése világos, ha az f függvényt mindenhol definiáljuk. Ha nem, akkor értse meg őket az alábbiak szerint: g (x1. Xk) értéke y. ha f (x1 .xk, y) van definiálva és nullával egyenlő, és az y (y), y ' A jelölést gyakran használják és ezért a minimalizálási operátort operátornak is nevezik. Nyilvánvaló, hogy ez a meghatározás biztosítja a g kiszámíthatóságát. ha f számítható (a y értéket növekvő sorrendbe rendezzük, várva, hogy megjelenjen a nulla érték). Mutassuk meg, hogy ha módosítja a definíciót, és engedélyezze f (x1. Xk, y ') definiálását y' A szubsztitúciós operátorok, az első primitív rekurzió és a minimalizálás segítségével az alapból (nulla, vetítés és egy egység hozzáadása) származó funkciók részben rekurzívak. Ha egy ilyen funkció mindenhol meghatározásra kerül, akkor általános rekurzív függvénynek nevezik. Az ilyen furcsa terminológia nyilvánvalóan az angol nyelvű fordítások eredményeként alakult ki. Angolul "primitív rekurzív függvények" voltak (primitív rekurzív függvények). Ezután egy mindenhol definiálható, kiszámítható feladat általánosabb fogalmát adták, és ezeket a funkciókat "általános rekurzív funkciónak" nevezték. Ezután részleges részfunkciókat kezdték el, "részleges rekurzív függvényeknek" nevezve. Az orosz nyelvben a "részleges" szó rossz helyre esett, és a részleges rekurzív függvények helyett részleges rekurzív funkciókról kezdtünk beszélni. Ugyanez a sors jelent meg az "általános" szónak, amely furcsán lépett be az "általános rekurzív" melléknévre, és azt jelenti, hogy a funkciót mindenhol meghatározzák. Tétel 76. Minden funkció. számolható egy Turing-gépen, részben rekurzív. Legyen f kiszámítható egy Turing-gép segítségével (ezt a gépet M-vel jelöljük) egy argumentum függvényében. Tekintsük a T tulajdonságot (x, y, t). amely abból áll, hogy az M bemeneten lévő M gép az y válaszlást legfeljebb t időben adja meg. Amint fent láttuk, a Turing-gép bemeneténél és t időben lehetséges egy pillanat alatt számszerűsíteni állapotát primitív rekurzív módon; világos, hogy meg lehet tudni, hogy befejezték-e a munkát, és ha igen, vajon a válasz y volt-e. Így a T tulajdonság primitív rekurzív. Most kombináljuk az y és t argumentumokat egy párt a primitív rekurzív számozás segítségével; egy primitív rekurzív T 'függvényt kapunk. amelyre T '(x, [y, t]) = T (x, y, t); Most meg tudjuk írni, hogy hol p1 adja meg az első kifejezést a páros számmal, és azt jelenti, hogy "a legkisebb z, amire". Így az f függvény részben rekurzív. Az ellentétes is igaz: 77 tétel. Minden részleges rekurzív függvényt kiszámíthatunk egy Turing-gépen. Ez könnyű írni egy programot, véges számú változót, számológépek semmilyen parciális rekurzív függvény (helyettesítés csökkenti az egymást követő programok végrehajtásához, mint például a rekurziót ciklus egy, miközben minimalizálja a ciklusra. Mindkét típusú ciklus könnyen megvalósítható egy átmeneti üzemeltetők). Ezt követően csak arra kell utalnia, hogy minden funkció. amelyet egy véges számú regiszterrel számolnak, számítható egy Turing-gépen (amint azt a 10.2 fejezetben, a 66. tételben láttuk). Ezért, ha hiszünk „Turing tézis”, amely kimondja, hogy minden számolható függvény kiszámítható egy Turing-gép, hinned kell a „Egyház tézis” (Minden kiszámítható függvény parciális rekurzív), hogy ezek a pontok egyenértékűek. Valójában a történet itt bonyolultabb, és így leírható. A primitív rekurzív függvény meghatározását a nagy logikus Kurt Gödel adta meg, és technikai eszközként használta fel Gödel teljességi tételének igazolását az 1930-as évek elején. Azt is megadta egy általános rekurzív függvény definícióját (amely nem egyezik meg az adott, de azzal egyenértékű funkcióval). Az amerikai logikus Alonzo Church megfogalmazta tézisét mindenhol meghatározott funkciókra. feltételezve, hogy minden kiszámítható, mindenütt meghatározott függvény általános rekurzív. Ezután az amerikai Kleene matematikus azt javasolta, hogy kiterjessze ezt a disszertációt olyan funkciókra, amelyek nem mindenhol vannak meghatározva. Ezzel párhuzamosan az angol matematikus Turing és az amerikai matematikus Posta kínált modell elméleti számítógépek (Turing-gép és Post), csak abban különböznek, néhány részletet, és azt javasolta, hogy ezek a gépek lefedik az egész osztály az algoritmikus eljárások. Hamarosan kiderült, hogy az ilyen gépekre vonatkozó funkció kiszámíthatósága megegyezik a részleges rekurzivitással. (A történeti részletek megtalálhatók Kleene könyvében [4].) Mindenesetre, most a "Turing-értekezés", "egyházi tézis", "posztdokumentum" stb. általában szinonimaként használjuk: tézisek azt állította, hogy ösztönösen megértette az osztály kiszámítható parciális függvények egybeesik a hivatalos meghatározása az osztály részleges rekurzív függvények (Church tézise) kiszámítható a Turing-gép funkciók (Turing tézis), stb Ezzel a megértéssel bizonyítható az összes ilyen tézis egyenértékűsége, hiszen minden ismert formalizálási meghatározás (részleges rekurzivitás, Turing-gépek stb.) Ugyanazt a funkciócsoportot eredményezi. (Megjegyezzük, futólag, hogy egy másik számítási modellt normális algoritmusok. Or Markov algoritmust. Kínáltak Andrei Andrejevics Markov, Jr. (fia a nagyobbik, ami után nevezte Markov láncok és Markov-folyamatok). Ez volt az 1950-es. Mark írta szó algoritmus „f”. a vonatkozó elv (mindegyik algoritmus megegyezik a normál), hívta elve normalizálás. munkáiban, normális algoritmusokat használt konstrukció kibékíthetetlen asszociatív kalkulus. Sőt, valójában Markov írjon ki l minden részletet egy egyetemes algoritmus tervezése és volt a pontos bizonyítéka annak helyességét, úgy tűnik, ez a teljesítmény egyáltalán nem ismétlődő senki nem volt a kitartás valamilyen programozási nyelven írni nyelvén tolmácsa és hivatalosan bizonyítani helyességét).
Kapcsolódó cikkek