Pytanie, czy wszystkie różne odmiany maszyn Turinga są równoważne pod względem wydajności obliczeniowej, jest fundamentalnym pytaniem w dziedzinie informatyki teoretycznej, szczególnie w badaniach teorii złożoności obliczeniowej i rozstrzygalności. Aby rozwiązać ten problem, należy wziąć pod uwagę naturę maszyn Turinga i koncepcję równoważności obliczeniowej.