Cunoștințe, prelegere, funcții recursive

Mașini Turing și funcții recursive

Am analizat câteva tehnici diferite pentru construirea funcțiilor primitive recursive. Cu toate acestea, rămâne neclar cât de departe este această clasă. Acum arătăm că include toate funcțiile destul de rapid calculate.







Teoremă 75. Orice funcție. calculată pe o mașină Turing nu mai mult decât un timp primitiv recursiv (din lungimea intrării), este primitiv recursiv.

Reamintim că luăm în considerare intrarea și ieșirea cuvintelor de la mașinile Turing de la zero și de la zero. Deoarece argumentele și valorile funcțiilor primitive recursive sunt numere, teorema va avea sens doar dacă suntem de acord să identificăm numere și cuvinte. După cum am menționat deja, identificăm numărul n cu cuvântul obținut după eliminarea bitului de înaltă ordine 1 în expansiunea binară a numărului n + 1.

Când am simulat funcționarea mașinilor Turing cu programe, am codificat starea aparatului în patru numere (codul din partea stângă a benzii, codul din partea dreaptă a benzii, statul și litera sub cap). În același timp, această codificare a fost convenabilă. partea stângă a benzii am numărat ca număr în sistemul numeric, în care baza este egală cu numărul de caractere din alfabetul mașinii, iar spațiul este considerat zero; cu partea dreaptă a casetei, am făcut același lucru, doar în ordinea inversă (ordinea inferioară a capului). În acest caz, adăugarea sau îndepărtarea simbolului de la cap corespunde unei operații aritmetice simple (eliminând întregul diviziune, adăugând înmulțirea la baza sistemului de numere și adăugarea acestuia). Cu această codificare, funcțiile de tranziție (patru funcții ale a patru argumente care arată următoarea stare ca o funcție a celei anterioare) sunt scrise cu formule simple și primitive recursive.

Acum, luați în considerare funcția de tranziție iterativă, care indică care va fi starea mașinii Turing după pașii t. Mai precis, există patru funcții de cinci argumente (primele patru argumente codifică starea, al cincilea este numărul de pași). Definiția lor are forma unei recursiuni comune, pe care tocmai am dezmembrat. Prin urmare, aceste funcții sunt primitive recursive. Vom presupune că, după apariția stării finale, configurația mașinii nu se schimbă. Dacă știm că numărul de pași de lucru este limitat de o funcție primitivă recursivă. atunci este suficient să o înlocuiți cu al cincilea argument (numărul de pași) pentru a vă asigura că configurația finală a mașinii este o funcție primitivă recursivă din configurația sa inițială. În consecință, rezultatul lucrării este o funcție primitivă recursivă a datelor inițiale.

Acest raționament implicit folosește recursivitatea primitivă a diferitelor funcții asociate tranziției de la o prezentare a datelor la alta. De exemplu, introducerea unei mașini Turing este un cuvânt binar, pe care am convenit să îl identificăm cu un număr x. Această intrare corespunde configurației inițiale a mașinii Turing, pe care o codificăm cu un număr de patru cifre. Este important pentru noi ca această cvadruplu să depindă în mod primitiv la x. Acest lucru este ușor de înțeles, deoarece transformarea este asociată cu o tranziție de la un sistem de număr la altul (același cuvânt codifică numere diferite în sisteme de numere diferite); Recursivitatea primitivă a unor astfel de funcții poate fi stabilită cu ușurință folosind metodele descrise mai sus. În plus, trebuie să extragem rezultatul din configurația de ieșire și să îl recodezim, de asemenea, și să obținem lungimea de la intrare (pentru a înlocui o funcție primitivă recursivă care limitează numărul de pași). Dar toate acestea, de asemenea, nu ies din cercul metodelor discutate mai sus și nu vom mai vorbi în detaliu.

Această teoremă ne convinge de recursivitatea primitivă a multor funcții destul de dificile definite. De exemplu, ia în considerare funcția n (a zecea cifră n-a unui număr). Este cunoscut faptul că milioane de astfel de semne calculate, astfel încât există toate motivele să creadă că anumiți algoritmi de lucru nu a fost prea lung ar fi foarte ciudat dacă în timpul activității lor (chiar și cu inconvenientul unei mașini Turing pentru programare) nu poate fi estimată, de exemplu, funcția CX2 n pentru c. Și o astfel de estimare este recursivă primitivă, ceea ce ne permite să ne referim la teorema tocmai dovedită. (De fapt, aici sunt funcții primitive recursive care cresc mult mai repede decât 2 n.)

O altă descriere a clasei funcțiilor primitive recursive. mai mult programator prietenos: ea funcții care pot calcula programul care cuprinde, dacă-then-else și -vetvleniya pentru -cycles, dar nu conțin în timp ce -cycles (și, prin urmare, du-te la rău și diverse alte tipuri de modificări în buclă pentru- într-un parametru de buclă) .







87. Stați și dovediți declarația corespunzătoare.

Funcții parțial recursive

Operatorii de recursiune primitivă și substituire nu ne duc în afara clasei de funcții definite peste tot. Nu este cazul operatorului de minimizare. despre care am menționat deja. Este aplicată funcției libere (k + 1) f și dacă k - funcția locală g. definit după cum urmează: g (x1. xk) este cel mai mic y. pentru care f (x1 .xk, y) = 0.

Semnificația cuvintelor selectate este clară dacă funcția f este definită peste tot. Dacă nu, atunci le înțelegeți după cum urmează: valoarea lui g (x1, Xk) este egală cu y. dacă f (x1 .xk, y) este definită și egală cu zero și toate valorile f (x1, yk, y ') pentru y'

Notatia este adesea folosita

și, prin urmare, operatorul de minimizare este, de asemenea, numit -operator.

Este clar că această definiție asigură calculabilitatea g. dacă f este calculată (ordonăm tot y în ordine ascendentă, așteptând apariția valorii zero).

88. Aratati ca daca schimbati definitia si permiteti f (x1, Xk, y ') sa fie nedefiniti pentru y'

Funcțiile obținute de la bază (zero, proiecție și adăugare a unei unități) folosind operatori de substituție, recursiune primitivă și minimizare, sunt numiți parțial recursivi. Dacă o astfel de funcție este definită peste tot, atunci se numește o funcție generală recursivă.

O astfel de terminologie ciudată, aparent, sa dezvoltat ca urmare a traducerilor din limba engleză. În limba engleză existau "funcții primitive recursive" (funcții primitive recursive). Apoi, a fost dat un concept mai general (general) al unei funcții definite peste tot, și astfel de funcții s-au numit "funcții generale recursive". Apoi au început să ia în considerare funcțiile partiale parțiale, numindu-le "funcții parțiale recursive". În limba rusă, cuvântul "parțial" a căzut într-un loc greșit, și în loc de funcții parțial recursive, am început să vorbim despre funcții parțial recursive. Aceeași soartă a fost cuvântul "general", care a intrat ciudat în adjectivul "general recursiv" și înseamnă că funcția este definită peste tot.

Teorema 76. Fiecare funcție. calculată cu o mașină Turing, este parțial recursivă.

Fie f calculul prin intermediul unei mașini Turing (această mașină desemnează M), o funcție a unui argument. Luați în considerare proprietatea T (x, y, t). constând în faptul că mașina M la intrarea x dă răspunsul y într-un interval de timp nu mai mare de t. După cum am văzut mai sus, la intrarea mașinii Turing și în timp t, este posibil să se calculeze starea sa într-un moment t într-un mod primitiv recursiv; este clar că se poate afla și dacă a fost finalizată lucrarea și dacă da, dacă răspunsul a fost y. Astfel, proprietatea T este recursivă primitivă.

Acum combinăm argumentele y și t într-o pereche cu ajutorul numerotării primitiv recursive; obținem o funcție primitivă recursivă T '. pentru care T '(x, [y, t]) = T (x, y, t); Acum putem scrie unde p1 își dă primul termen prin numărul de perechi și înseamnă "cel mai mic z pentru care". Astfel, funcția f este parțial recursivă.

Conversia este de asemenea adevărată: Teorema 77. Fiecare funcție parțială recursivă poate fi calculată pe o mașină Turing.

Este ușor de a scrie un program cu un număr finit de variabile, calcul orice funcție recursivă parțială (substituție reduce la punerea în aplicare succesivă a programelor, cum ar fi recursivitate la ciclul de minimizare în timp ce ciclu de tip. Ambele tipuri de cicluri pot fi ușor de pus în aplicare cu ajutorul unei operatori de tranziție).

După aceasta, rămâne doar să se facă referire la faptul că fiecare funcție. calculată printr-un program cu un număr finit de registre, este calculată pe o mașină Turing (așa cum am văzut în secțiunea 10.2, Teorema 66).

Prin urmare, dacă noi credem în „Turing teza“, care prevede că fiecare funcție calculabil este calculabil de o mașină Turing, trebuie să crezi în „teza Bisericii“ (fiecare funcție calculabil este recursiv parțială), astfel încât aceste puncte sunt echivalente.

De fapt, povestea aici este mai complicată și poate fi descrisă aproximativ ca aceasta. Definirea unei funcții primitive recursive a fost dată de marele logician Kurt Gödel și a fost folosită ca instrument tehnic pentru a dovedi teorema incompletenței lui Gödel la începutul anilor '30. De asemenea, el a dat definiția unei funcții generale recursive (care nu coincide cu cea dată, dar echivalentă cu ea). Logicianul american Alonzo Church și-a formulat teza pentru funcțiile definite peste tot. presupunând că fiecare funcție definită peste tot este comprehensivă recursivă generală. Apoi, matematicianul american Kleene a propus extinderea acestei teze la funcții care nu sunt definite peste tot.

În paralel, matematicianului englez Turing și matematicianul american post a oferit modelul de calculatoare abstracte (mașină Turing și Post), care diferă doar în unele detalii, și a sugerat că aceste mașini acoperă întreaga clasă de procese algoritmice. Curând a devenit clar faptul că calculele unei funcții pe astfel de mașini sunt echivalente cu recursivitatea parțială. (Detaliile istorice pot fi găsite în cartea lui Kleene [4].)

Oricum, acum expresia "teza Turing", "teza bisericii", "teza post", etc. de obicei folosite ca sinonime: aceste teze a susținut că a înțeles intuitiv clasa de funcții parțiale calculabile coincide cu definiția formală a clasei de funcții recursive parțiale (teza lui Church) calculabil de masini Turing funcții (teza Turing), etc. Cu această înțelegere, este posibil să se demonstreze echivalența tuturor acestor teze, deoarece toate definițiile formale cunoscute ale computabilității (recursivitate parțială, mașini Turing etc.) conduc la aceeași clasă de funcții.

(Menționăm în treacăt că un alt model de calcul algoritmi normali. Sau algoritmi Markov. S-au oferit Andrei Andreevici Markov, Jr. (fiul cel Bătrân, după care el a numit lanturi Markov si procese Markov). Acest lucru a fost în anii 1950. Mark a scris algoritm cuvânt prin „f“. principiul relevant (fiecare algoritm este echivalent cu normal), el a numit principiul normalizării. În lucrările sale, algoritmi normali folosite pentru a construi un calcul asociativ ireconciliabilă. Mai mult decât atât, Markov a scrie în mod efectiv l în toate detaliile unui design de algoritm universal și a avut dovada exactă a corectitudinii sale, se pare, această realizare nu este deloc repetată nimeni altcineva nu a avut perseverenta de a pentru un limbaj de programare pentru a scrie în limba interpretul său și în mod oficial dovedi corectitudinea acesteia).







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: