În matematică și informatică , o mașină Zeno (uneori scurtată la 3M , numită și mașină Turing accelerată ) este un model computerizat ipotetic asociat cu o mașină Turing care este capabilă să facă un număr numărabil de pași algoritmici într-un timp finit. În majoritatea modelelor de calcul, astfel de mașini nu sunt luate în considerare.
Mai strict, o mașină Turing este o mașină Zeno care necesită 2 - n unități de timp pentru a finaliza pasul al n -lea. Astfel, primul pas necesită 0,5 unități de timp, al doilea 0,25, al treilea 0,125 și așa mai departe, astfel încât se fac un număr infinit de pași pe unitatea de timp.
Ideea unei mașini Zeno a fost discutată pentru prima dată de Hermann Weyl în 1927. Și-a primit numele în onoarea aporiei filosofului grec antic Zenon din Elea . Astfel de mașini joacă un rol cheie în unele teorii. De exemplu, teoria punctului Omega a lui Frank Tippler este corectă numai dacă mașina Zeno poate exista.
Unele funcții care nu pot fi calculate pe o mașină Turing pot fi calculate folosind o mașină Zeno. De exemplu, problema opririi poate fi rezolvată pe ea (după cum este ilustrat de următorul pseudocod ):
pornirea programului scrie 0 în prima celulă de pe bandă; începerea ciclului simulați următorul pas al mașinii Turing date la intrarea dată; dacă mașina Turing s-a oprit, atunci scrieți 1 în prima celulă de pe bandă și întrerupeți bucla ; sfârşitul buclei sfârşitul programuluiAstfel de calcule, dincolo de capacitatea unei mașini Turing, sunt numite hipercalculare .
Este de remarcat faptul că problema de oprire pentru mașina Zeno în sine nu poate fi rezolvată pe mașina Zeno (Potgieter, 2006).