Upit o tome jesu li sve različite varijacije Turingovih strojeva ekvivalentne u računalnim sposobnostima temeljno je pitanje u polju teorijske računalne znanosti, posebno unutar proučavanja teorije složenosti računanja i mogućnosti odlučivanja. Da bismo to riješili, bitno je razmotriti prirodu Turingovih strojeva i koncept računalne ekvivalentnosti.