Turingov stroj je osnova na kojoj je nastalo današnje računalo.

Tko god danas uključi računalo, radi na nečemu što je u osnovi Turingov stroj.

Pokazuje se da je zbog nje pitanje odlučivosti popločavanja ravnine (" Postoji li algoritam koji za dani skup pločica određuje je li moguće njima popločati ravninu? ") ekvivalentno pitanju odlučivosti zaustavljanja Turingovog stroja (" Postoji li algoritam koji određuje hoće li dani Turingov stroj stati nakon konačno mnogo koraka? ").

Uzmemo li tezu kao istinitu, za dokazati Turing-potpunost nekog programskog jezika ili apstraktnog modela izračunavanja dovoljno je pokazati (najčešće efektivnom konstrukcijom) da je u njemu moguće simulirati univerzalni Turingov stroj.

Posebice, parcijalna funkcija f definirana tako da f (n) = m ako i samo ako Turingov stroj sa indeksom n koji staje na ulazu 0 sa izlazom m nema proširenja na totalno izračunljivu funkciju.

Nedeterministički Turingov stroj (u daljnjem tekstu: NTS) radikalni je odmak od tog principa, kao što je, da povučemo ne posve neosnovanu analogiju sa stvarnošću, masivno paralelno računalo znatno kompleksniji i moćniji sustav od klasične sekvencijalne arhitekture.

" Strong AI " hipoteza kaže da je um prema mozgu ono što je softver prema hardveru; da je hardver implementacija turingovog stroja, a softver pravila (program) za turingov stroj.

Turingov stroj koji može simulirati bilo koji drugi Turingov stroj se zove Univerzalni Turingov stroj (UTS ili jednostavno univerzalni stroj).

Kažemo da je problem L \ in \ oplus P ako postoji nedeterministički Turingov stroj M takav da za sve ulazne riječi x vrijedi x \ in L ako i samo ako Turingov stroj M s ulazom x ima neparan broj stanja u kojima prihvaća riječ x ([ 7 ]).

Postoji Turingov stroj U takav da za svaki Turingov stroj M i bilo koju riječ w nad njegovom abecedom vrijedi: stroj U s ulazom (M, w) staje ako i samo ako staje stroj M s ulazom w i pritom oba stroja daju isti izlaz.

Za U kažemo da je univerzalni Turingov stroj.

Zapitajmo se sljedeće: postoji li Turingov stroj H koji radi kao " automatski verifikator "?

Za bilo koji Turingov stroj M i njegov ulaz w, stroj H odlučuje prihvaća li M riječ w.

Ekvivalentno pitanje je da li je jezik L = (M, w) M je Turingov stroj koji prihvaća w rekurzivan?

No, L jest rekurzivno prebrojiv jer ga univerzalni Turingov stroj U prepoznaje.

Pokažimo sada da takav Turingov stroj H ne postoji

Konstruirajmo Turingov stroj E (enumerator), koji ispisuje sve riječi iz L.

Σ (n): najveći broj jedinica koje može ispisati Turingov stroj s n stanja prije nego što stane.

Izgradimo Turingov stroj M, koristeći Kleeneov rekurzijski teorem, koji za ulaz 0 simulira stroj sa indeksom e pokrenut na indeksu n M za M (stoga stroj M može proizvesti sam svoj indeks; ovo je svrha rekurzijskog teorema).

Općenito Turingov stroj izračunava neku parcijalnu funkciju.

Dva Nizozemska istraživača od lego kockica su napravili Turingov stroj, koncept rada računala koji je osmislio Alan Turing 1936. godine.

Nedeterministički Turingov stroj se od determinističkog razlikuje po funkciji prijelaza i završnim stanjima koja slijede princip podjele na prihvaćajuće (A) i odbacujuće (R).

Za parcijalnu funkciju f iz N u 0, 1 kažemo da je Turing-izračunljiva ako postoji Turingov stroj koji je izračunava.

Turingov stroj (u daljnjem tekstu: TS) fundamentalni je apstraktni model izračunavanja.

Za jezik L nad alfabetom Σ kažemo da je rekurzivan ili Turing-odlučiv, ako postoji Turingov stroj M s ulaznim alfabetom Σ koji ulaznu riječ w nad Σ prihvaća točno kad je w L, a u suprotnom je odbacuje.

Turingov stroj za povećavanje binarnog broja

S bila izračunljiva, tada bi znali da svaki Turingov stroj s n stanja, ako nije stao u S (n) koraka, nikada neće stati.

Dosad nije pronađena niti jedna funkcija za koju bi se svatko složio da je izračunljiva, ali za nju dokazano ne postoji pripadni Turingov stroj.

Manje formalno, Turingov stroj sastoji se od beskonačne trake i glave koja s nje čita i na nju piše simbole iz alfabeta Γ.

Sa druge strane, informatičari barataju pojmovima kao što je Turingov stroj, heuristika i tako dalje, te su po meni mjerodavni razgovarati i o pojmu svijesti (baš kao i filozofi ili nedaj bože psiholozi).