Definirea unui algoritm bazat pe automate abstracte (mașină Turing)
Definiția unui algoritm bazat pe funcții recursive
Recurgerea este procesul de definire a unei funcții, în care valoarea sa pentru valorile arbitrare ale argumentelor este exprimată într-un mod cunoscut prin valorile funcției pentru valori mai mici ale argumentelor.
Funcția pentru care există un algoritm de evaluare pentru orice argument din domeniul definiției funcției este numit computable.
O funcție pentru care există o procedură eficientă pentru calculul acesteia bazată pe recursivitate este numită recursivă.
Clasa funcțiilor recursive este identică cu clasa funcțiilor computabile definite universal - teza bisericii.
O funcție, definită nu pentru toate valorile argumentelor, dar numai pentru un anumit subset, se numește o funcție parțială.
Toate funcțiile parțiale calculate de algoritmi sunt parțial recursive - teza lui Kleene.
Conceptul de funcții parțial recursive este folosit pentru a dovedi solvabilitatea algoritmică sau insolvabilitatea problemei.
Procesele algoritmice sunt procese pe care o "mașină" potrivită poate să le îndeplinească.
Prin "mașină" în acest caz se înțelege un abstract, existent numai în mașina de imaginație.
În general, o astfel de mașină constă din următoarele părți:
- de la banda de informații nelimitată în ambele părți, împărțită în celule, reprezentând memorie nelimitată a mașinii. În fiecare celulă, puteți stoca un singur caracter, inclusiv zero;
- din capul de citire / scriere de-a lungul căruia se poate deplasa banda;
- Dispozitivul de control, care în fiecare moment considerat este într-o anumită "stare". Dispozitivul de control poate fi într-un număr limitat de state finite, dacă această stare este finală, mașina termină să funcționeze.
O astfel de mașină poate deplasa banda cu o celulă la stânga sau la dreapta, lăsând conținutul celulelor neschimbate sau poate schimba starea celulei percepute, lăsând banda staționară. Mașina Turing funcționează într-un alfabet arbitrar finit și efectuează un număr finit de ordine.
Mașinile Turing sunt executori universali, cu ajutorul cărora puteți simula toate procesele algoritmice descrise de matematicieni. Sa demonstrat că clasa funcțiilor calculate pe aceste mașini coincide exact cu clasa tuturor funcțiilor parțial recursive. astfel chestiunea existenței sau inexistenței unui algoritm pentru o problemă de un tip sau altul ar trebui înțeleasă ca o chestiune a existenței sau inexistenței unei mașini Turing care posedă proprietatea necesară.
Înțelegerea intuitivă a mașinii Turing este următoarea: există o bandă infinită, împărțită în celule. Căruța merge cu cuști. După citirea literei scrise în cușcă, carul se mișcă spre dreapta, spre stânga sau rămâne în poziție, în timp ce litera este înlocuită cu una nouă. Unele litere opresc carul și închis.
Există mai multe moduri de înregistrare a algoritmilor care diferă una de cealaltă prin vizibilitatea, compactitatea și gradul de formalizare. Cele mai răspândite: verbal, grafic, software.
Metoda grafică de înregistrare implică utilizarea anumitor simboluri grafice - blocuri, fiecare dintre acestea indicând un anumit tip de acțiune.
Fiecare bloc prevede executarea anumitor acțiuni. Setul de blocuri formează un algoritm sau o diagramă bloc.
Desemnarea unor blocuri în conformitate cu GOST 19.701-90 SCHEME DE ALGORITME, PROGRAME DE DATE ȘI SISTEME
Articole similare
Trimiteți-le prietenilor: