što je zanimljiva sama po sebi, mogućnost implementiranja Turingovih strojeva Wangovim pločicama ima još jednu posljedicu .
. Ovdje opisani načini nisu doslovne implementacije Turingovih strojeva jer ne provode račun "iz reda u red" ,
dva stroja za koja je bio uvjeren da su nastala na osnovu Turingovih zamisli. Ubrzo sam počeo pisati programe za ta prva
tu spominjalo, od kompjutera koji komponira glazbu, preko Turingovih strojeva pa do fenomena intuicije. Znanost ima
je odmah vidljivo da postoji prebrojivo mnogo različitih Turingovih strojeva. Rad Turingova stroja Primijetimo da je za svaki t
", pokazat ćemo dva ekvivalentna načina programiranja Turingovih strojeva na primjeru TS-a koji povećava ulazni broj u
i programske zadatke čitatelje upućujemo na simulatore Turingovih strojeva [ AV ] ili [ DS ]. Još dva primjera za prvi simulator
bilo koje od funkcija tape, head i cfg. 2. Varijante Turingovih strojeva Turingovi strojevi definiraju se na mnogo
, sve te definicije ekvivalentne. Ipak, neki su modeli Turingovih strojeva "brži" od drugih na raznim klasama problema, što
Stroj D možemo shvatiti kao "dijagonalni komplement" . Turingovih strojeva ima prebrojivo mnogo, pa je skup svih TS-ova
P iz izreke teorema možemo shvatiti kao opis nekog svojstva Turingovih strojeva, u smislu da P sačinjavaju kodovi onih strojeva
svojstvo nije trivijalno. Dakle, netrivijalna svojstva Turingovih strojeva su neodlučiva Jedno takvo svojstvo, koje ne ovisi
primjer π i e, također Turing-izračunljivi. No, budući da Turingovih strojeva ima prebrojivo mnogo, a realnih brojeva
da bez smanjenja općenitosti možemo za alfabet svih Turingovih strojeva uzeti binarne znamenke. Definiramo tzv. Busy
neki modeli izračunavanja koji su uistinu jači od Turingovih strojeva, niti jedan ne odgovara temeljnoj intuiciji