Funcții recursive primitive (PRF)

Definiția. Funcții elementare sunt numite:

1) funcția constantă. unde n = 0,1,2, ..., q = 0,1,2, .... în special funcția de zero.

2) Următoarea funcție.

3) selectați funcția. în care 1≤ m ≤ n, n = 1,2, ....

Toate funcțiile elementare - definite peste tot și algoritmic

calculabil. Există un număr mic de operații asupra funcțiilor elementare care sunt funcții calculabil calculabil din nou.

substituție Operation (superpoziție)

Având în vedere o funcție și funcția. Se spune că funcția derivată din aceste funcții prin înlocuirea operațiunii, dacă următoarea ecuație

și este notat cu. unde S - este operațiunea de substituție.

Exemplu. Să. atunci

Principalele proprietăți ale operației de substituție

1. Operația de substituire păstrează proprietatea funcțiile definite peste tot, adică. E. Dacă funcția g (y1, ..., ym) și funcțiile h1 (x1, ..., xn), h2 (x1, ..., xn), hm (x1, ..., xn) funcție definită peste tot f și funcția care este obținut prin operația de substituție, atunci f este, de asemenea, o funcție definită peste tot.

2. Operațiunea de înlocuire păstrează proprietatea calculabilitate algoritmică a funcțiilor, și anume Dacă funcția g (y1, ..., ym) și h1, ..., hm sunt algoritmic calculabil și f = S (g; h1, ..., hm), atunci există un algoritm Af. calculează funcția f.

Operația recursivitatii primitiv

Fie funcția și funcția.

Definiția. Se spune că funcția obținută din funcțiile, și prin funcționarea recursivitatii primitiv în cazul în care dețin egalitățile:

Acest lucru are sens când n ≠ 0, înregistrat

Când specificați o descriere primitivă funcție recursivă. independent de un sistem de variabile recursiune primitiv are forma

Class PRF toate funcțiile recursive primitive este un set de funcții care pot fi obținute din funcțiile inițiale prin superpoziție și recursie primitiv.

Proprietățile de bază ale recursivitatea primitiv de funcționare

1) Operațiunea recursie primitivă, precum operația de substituție păstrează proprietatea pretutindeni certitudinea și calculabilitate algoritmice.

2) Conservarea funcțiilor algoritmice calculabilitate.

Exemplu. Aplicați operația recursivitatii primitiv la funcția. Funcția scrisă sub forma „analitică“.

Decizie. . . Conform funcționării primitive recursiv. .

Să pas mii să fie adevărat. atunci

Astfel, ca rezultat al recursie primitive.

III. mașină Turing

Algoritmul - este definit pe unele instrucțiuni limbaj finit (reteta de proces), care specifică secvența de discretă executabil de operații elementare pentru a rezolva problema. Procesul de executare instrucțiuni constă în etape separate, fiecare dintre care deține o operațiune următoare.

La baza acestuia, algoritmul are un proces mecanic de prelucrare a informațiilor. Pentru prima dată, Alan Turing a definit conceptul unui algoritm bazat pe conceptul de mașină care funcționează în mod automat; Mai mult decât atât, el a propus un model formal al dispozitivului, care este intuitiv simulează acțiunile umane rezolvă problema, ghidat de unele algoritm. Acest dispozitiv a fost numit o mașină Turing.

Într-un dispozitiv de calcul Turing modelata condus la operațiile de bază ale procesului de implementare a unei persoane algoritm arbitrar. Omul are o memorie finită, și în acest sens, este posibil să ne imaginăm un sistem cu un număr finit de stări. Informații generale privind algoritmul este de obicei reprezentat ca un șir de caractere. Se poate imagina că aceste informații sunt prezentate sub forma de cuvinte (secvența finală de caractere) într-un vocabular finit. Efectuarea unui calculator persoană algoritm utilizează memorie suplimentară (care poate fi potențial infinit, de exemplu hârtie) pentru înregistrarea de informații, iar această înregistrare se realizează caracterul secvențial cu caracter. În calculele, o persoană poate reveni la informațiile înregistrate anterior, ștergând unele informații, etc. Astfel, atunci când operațiile elementare ale algoritmului poate presupune o înregistrare caracter și ștergerea, precum și trecerea atenția de la o zonă de înregistrare la alta. Turing modelul propus are o bandă de lucru infinit, care citește și scrie caractere și în cazul în care un cap de citire-scriere, care se pot deplasa pe banda de lucru în orice direcție.

mașină Turing Vom descrie acum mai bine. Mașina are un număr finit de cifre (caractere, litere), formând așa-numitul alfabet extern A =. În fiecare celulă a panglicilor studiate în fiecare punct de discret în timp pot fi înregistrate doar un simbol al alfabetului A. Din motive de uniformitate este convenabil să se presupună că printre literele alfabetului A, există un extern „scrisoare goală“, și că este înregistrată în celula goală a benzii. Suntem de acord că „scrisoare gol“ sau simbolul celulelor goale este litera # 923;. Banda se presupune nelimitat în ambele direcții, dar la un moment dat pe ea în scris non-gol număr finit de litere

În plus, de fiecare dată când aparatul este în măsură să fie într-o stare a unui număr finit de stări interne, care set de Q =. inițială q1 și finală Q0 (sau de stat opri) - alocate între cele două state. Fiind în q1 de stat, aparatul începe să funcționeze. Odată ajuns în stare Q0, aparatul se oprește.

Funcționarea mașinii determinată de program (schema bloc funcțională). Programul este format din comenzi. Fiecare echipa T (i, j) (i = 1, 2 n; j = 0, 1. m) este o expresie a unuia dintre următoarele tipuri :. în cazul în care. și X =.

Data viitoare (în cazul în care qk ≠ Q0) masina face un pas,

comandă reglementată T (l, k): alqk → asqrX etc.

Deoarece funcționarea mașinii, prin ipoteză, este complet determinat de qj său de stat în momentul și conținutul examinat celulele în acest moment, apoi pentru fiecare QJ și ai, (i = 1, 2 n; j = 0, 1. m) programul mașinii trebuie conțin una și doar o singură comandă de pornire simboluri qiaj. De aceea Turing programul Machine cu alfabet A = stări exterioare și interioare cuprinde alfabet Q = m (n + 1) de comandă.

Un cuvânt în alfabetul sau alfabet Q sau alfabet AUQ se referă la orice secvență a alfabetului corespunzătoare. Sub configurația k ne referim la imaginea benzii mașinii cu informațiile existente pe acesta la începutul etapei k (sau un cuvânt în alfabetul A, înregistrat pe bandă la începutul etapei k), indicând care celula este inspectată în această etapă și starea mașinii. Au o semnificație numai la configurația finală, și anume, cele în care toate celulele bandă, cu excepția, eventual, pentru un număr finit, gol. Configurația se numește finală, în cazul în care starea în care se află în mașina, finală.

Dacă selectați oricare nu configurația finală a mașinii Turing ca originalul, mașina de lucru va consta în faptul că seria (pas cu pas) pentru a converti configurația originală, în conformitate cu programul mașinii până la până când ajunge la configurația finală. După aceea, activitatea unei mașini Turing este considerat încheiat, iar rezultatul lucrării este considerat a ajunge la configurația finală.

Noi spunem că un cuvânt care nu este gol # 945; în alfabetul A \ = mașină percepută în poziția normală, în cazul în care se înregistrează în benzi succesive de celule, toate celelalte celule sunt goale, iar aparatul scanează celula de la extrema dreaptă cele în care cuvântul scris # 945;. Poziția standard, este numit inițial (final) în cazul în care mașina, să ia cuvintele în poziția normală, este în stare inițială q1 (respectiv Q0 stare de oprire). În cele din urmă, noi spunem că cuvântul # 945; Mașini de prelucrare pentru cuvânt # 946;, în cazul în care cuvântul # 945;, percepută în poziția standard inițială, aparatul după un număr finit de echipe care vin la cuvântul # 946;, percepută în poziția de oprire.