Ancheta cu privire la faptul dacă toate variațiile diferite ale mașinilor Turing sunt echivalente în capacitatea de calcul este o întrebare fundamentală în domeniul informaticii teoretice, în special în studiul teoriei complexității computaționale și al decidebilității. Pentru a aborda acest lucru, este esențial să luăm în considerare natura mașinilor Turing și conceptul de echivalență computațională.