maşină Turing

Maşinile Turing sunt nişte 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. 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 a fost niciodată construite. Studiul proprietăţilor lor abstracte este util în informatică şi teoria complexităţii.