Rozważania na temat mocy obliczeniowej niedeterministycznych maszyn Turinga są podstawą centralnego problemu teorii złożoności obliczeniowej – „P versus NP”.
Mimo że maszyna Turinga jest abstrakcją o dużej mocy obliczeniowej (większej na przykład niż dowolny komputer), istnieje wiele problemów (np. problem stopu), których nie da się na niej rozwiązać. Matematycy rozważają więc (od czasów samego Turinga) silniejsze modele obliczeń, które mogą takim zadaniom podołać. Hipotetyczne maszyny potrafiące wykonywać takie obliczenia, nazywa się hiperkomputerami. Należy zauważyć, że przy obecnym stanie wiedzy nie jest jasne, czy prawa fizyki rządzące naszym światem pozwalają na skonstruowanie maszyn obliczeniowych silniejszych niż maszyna Turinga. Jest to pole aktywnych prac badawczych.
Zapis formalny thumb|350px|Grafika przedstawiająca maszynę Turinga w stanie q1 nad zerem na taśmie Formalnie maszynę Turinga opisuje się poprzez krotkę: