Mașinile Turing sunt similare cu automatele finite/mașinile cu stări finite, dar au avantajul memoriei nelimitate … Sunt capabile să simuleze computere obișnuite; o problemă pe care o poate rezolva un computer obișnuit (cu o memorie suficientă) va putea fi rezolvată și folosind o mașină Turing și invers.
Care este diferența dintre RAM și TM?
O mașină Turing nu poate O mașină RAM poate face aritmetica în O(1) (sub anumite restricții). O mașină Turing nu poate. Mașinile Turing simulează polinomial mașini RAM, adică pentru o constantă c, orice mașină RAM care rulează în timp O(nk) poate fi simulată de o mașină Turing care rulează în timp O(nck).
Este banda unei mașini Turing nelimitată?
A Turing Machine (TM) este o mașină de stări care constă din două memorii: o bandă nelimitată și un tabel de control al stărilor finite. Banda conține date ca simboluri. Aparatul are un set foarte mic de operații adecvate, 6 (citește, scrie, mișcă la stânga, mișcă la dreapta, schimbă starea, opri) pe bandă.
De ce mașina Turing este puternică?
Cât de puternice sunt mașinile Turing? Mașinile Turing pot accepta orice limbaj obișnuit sau fără context. Mașinile Turing pot efectua calcule aritmetice de bază … Teza lui Turing afirmă că orice calcul care poate fi efectuat prin „mijloace mecanice” poate fi efectuat de o mașină Turing (ignorând problemele de eficiență).
Mașinile Turing pot face bucle pentru totdeauna?
turing(turingDescrip) nu poate nici să se oprească, nici să facă buclă pentru totdeauna; nici nu are sens.
