PARTEA II-a. AUTOMATE INFINITE. CALCULABILITATE — Cap. 5. Mașina Turing
După cum s-a arătat în Introducere Teoria automatelor consideră noțiunea de automat ca pe o formalizare a noțiunii de mașină de calcul. Modelul automatelor finite, prezentat în Partea a I-a, poate fi considerat ca un model general al clasei mașinilor cu memorie finită, putând servi ca un etalon în comparația cu mașinile de calcul reale, în măsura în care influențează funcționarea.
Din cele arătate în Partea I-a s-a putut vedea că funcționarea automatelor finite se caracterizează prin aceea că fiecare mișcare a automatului este complet determinată de starea sa internă și de simbolul de intrare citit în acel moment. În acest sens funcționarea este rigidă, automatul neavând inițiativă și creativitate, mașinii lipsindu-i imaginația și fantezia, proprii omului.
Se spune despre o astfel de funcționare că are un caracter mecanic, și de aici termenul de „mașină”. Acest termen are un caracter oarecum peiorativ, deoarece automatele sunt considerate niciodată foarte inteligente, comparația având ca etalon omul.
Pentru a defini mai precis noțiunea de funcționare mecanică a unei mașini reale trebuie luate în considerație două aspecte. Primul este cel al memoriei, care în cazul automatelor finite se reduce la un număr finit de stări interne, adică la o memorie finită. Al doilea aspect este cel al rigidității regulilor de funcționare, care în cazul automatelor finite este maximal.
În cazul mașinilor reale, memoria este de obicei finită, dar poate fi foarte mare, iar regulile de funcționare pot fi mai complexe. În teorie, pentru a discuta noțiunea de calculabilitate, este util să se introducă un model idealizat de mașină cu memorie infinită, dar cu reguli de funcționare complet determinate. Aceasta este mașina Turing.
În cele ce urmează se vor face referiri numeroase la un tip foarte cunoscut de mașină reală: calculatorul. Calculatorul va servi ca model intuitiv și ca punct de referință pentru discuțiile viitoare. Se știe că programul unui calculator nu este altceva decât o descriere a modului de prelucrare, într-un limbaj formal, a datelor. Programul descrie, într-o manieră precisă, pașii care trebuie executați, în ordinea stabilită de autor.
Funcționarea calculatorului reproduce într-un anumit sens funcționarea mașinii abstracte. Descrierea într-un limbaj de programare a modului de prelucrare a datelor este o descriere completă, în sensul că se știe în fiecare moment operația ce urmează să fie executată. De aceea este normal să se afirme că: orice calcul dintr-un calculator poate fi precis descris.
Mai puțin evidentă este afirmația inversă: orice procedură ce poate fi precis descrisă poate fi programată în vederea realizării ei de un calculator. Afirmația este bazată pe lucrările matematicianului Alan Turing referitoare la calculabilitate.
În ambele afirmații de mai sus noțiunea de „descriere precisă” este centrală. Turing a propus o formalizare a acestei noțiuni prin definirea unei clase de mașini ideale, care să fie capabile să execute orice procedură ce poate fi descrisă precis. Aceste mașini s-au numit mașini Turing.
Descrierea unei proceduri este o problemă ce a preocupat pe cercetători încă înainte de apariția calculatoarelor.
Evident, noțiunea de descriere presupune un anumit limbaj.
Se poate găsi un limbaj pentru descrierea tuturor procedurilor? Există proceduri care în ciuda unei cunoașteri perfecte nu pot fi descrise?
Toate aceste întrebări sunt legate de o noțiune foarte importantă: procedură efectivă sau algoritm.
