Maszyna Turinga okazuje się bardzo potężnym modelem obliczeń. Dodanie do maszyny dodatkowych możliwości nie zwiększa już klasy rozpoznawanych przez nią języków. Przykładowo wyposażenie maszyny w dodatkowe taśmy, używanie zamiast taśmy dwuwymiarowej płaszczyzny (i trójwymiarowej i dowolnie-wymiarowej), dodanie RAM, możliwości losowania i nawet obliczeń kwantowych – może być zasymulowane na zwykłej jednowymiarowej taśmie. Istnieje tzw. hipoteza Churcha-Turinga, mówiąca, że każdy fizycznie realizowalny komputer jest równoważny maszynie Turinga.
Problem stopu
Problem stopu jest jednym z najsłynniejszych problemów w informatyce, określającym możliwości wszystkich komputerów. Problem można sformułować w następujący sposób:
Mając dany opis maszyny Turinga i wejście, które ma do zanalizowania, określ czy maszyna ta kiedykolwiek się zatrzyma, czy też będzie działała w nieskończoność.
Można pokazać, że nie istnieje maszyna Turinga potrafiąca rozwiązywać ten problem dla dowolnych danych. Tym samym język złożony z par: (opis maszyny Turinga, słowo dla którego ta maszyna się zatrzymuje), nie jest językiem rekursywnym.