Mașină Turing
From Wikipedia, the free encyclopedia
Mașinile Turing sunt mecanisme extrem de elementare de dispozitive de prelucrare a simbolurilor care — în ciuda simplității lor — pot fi adaptate pentru a simula logica oricărui calculator ce poate fi construit. Modelele au fost descrise în 1936 de către Alan Turing.[1][2] Deși modelele erau proiectate inițial pentru a fi fezabile din punct de vedere tehnic, mașinile Turing nu au fost gândite pentru a fi tehnologii practice de calcul, ci un experiment mental despre limitele calculului mecanic; astfel, ele nu au fost niciodată construite. Studiul proprietăților lor abstracte este util în informatică și teoria complexității.[3]
Acest articol are nevoie de ajutorul dumneavoastră. Puteți contribui la dezvoltarea și îmbunătățirea lui apăsând butonul Modificare. |
O mașină Turing capabilă de a simula orice altă mașină Turing se numește mașină Turing universală (sau mașină universală). O definiție mai orientată matematic a fost introdusă de Alonzo Church, ale cărui lucrări din domeniul calculului lambda s-au împletit cu cele ale lui Turing într-o teorie formală a calculului cunoscută sub numele de Conjectura Church-Turing. Aceasta postulează că orice problemă de calcul bazată pe o procedură algoritmică poate fi rezolvată de către o mașină Turing. Deoarece nu se bazează pe o definiție precisă a conceptului de procedură algoritmică, nu are o formulare matematică. În schimb, este posibil de a se defini o noțiune de "sistem acceptabil de programare" și de a se demonstra că "puterea de calcul" a unui asemenea sistem este echivalentă cu cea a unei mașini Turing (se vorbește în acest caz de un limbaj de programare Turing-complet).