Turingov stroj

Turingovi strojevi su iznimno jednostavni apstraktni uređaji za manipulaciju znakovima (simbolima) koji - unatoč jednostavnosti dizajna - mogu biti prilagođeni da simuliraju logiku bilo kojeg računalnog algoritma (uz sadašnje poimanje algoritma). Opisao ih je 1936. Alan Turing. Turingovi strojevi ne koriste se u praktične svrhe, već u misaonim eksperimentima, gdje najvažniju primjenu nalaze u istraživanju granica mogućnosti izračunavanja računalnim algoritmima. Proučavanje njihovih svojstava pruža dalekosežne uvide u pitanja računalne znanosti i teorije složenosti.

Turingov stroj koji može simulirati bilo koji drugi Turingov stroj se zove Univerzalni Turingov stroj (UTS ili jednostavno univerzalni stroj). Više matematički orijentiranu definiciju sa sličnom "univerzalnom" prirodom je uveo Alonzo Church, čiji se rad na lambda računu isprepleo s Turingovim u formalnoj teoriji izračunljivosti poznatoj kao Church-Turingova teza. Teza povezuje strogu formalnu definiciju Turingovog stroja i intuitivne ideje izračunljivosti, te na taj način pruža preciznu definiciju algoritma ili 'mehaničkog postupka'.