Inom matematik och datavetenskap är en Zeno-maskin (ibland förkortad till 3M , även kallad en accelererad Turing-maskin ) en hypotetisk datormodell associerad med en Turing-maskin som kan ta ett räknebart antal algoritmiska steg på en begränsad tid. I de flesta datormodeller beaktas inte sådana maskiner.
Mer strikt är en Turing-maskin en Zeno-maskin som tar 2 − n tidsenheter att slutföra det n :e steget. Det första steget kräver alltså 0,5 tidsenheter, det andra 0,25, det tredje 0,125 och så vidare, så att ett oändligt antal steg tas per tidsenhet.
Idén om en Zeno-maskin diskuterades först av Hermann Weyl 1927. Den fick sitt namn för att hedra den antika grekiska filosofen Zeno av Elea aporierna . Sådana maskiner spelar en nyckelroll i vissa teorier. Till exempel är Frank Tipplers Omega Point -teori bara korrekt om Zeno-maskinen kan existera.
Vissa funktioner som inte kan beräknas på en Turing-maskin kan beräknas med hjälp av en Zeno-maskin. Till exempel kan stoppproblemet lösas på den (som illustreras av följande pseudokod ):
programstart skriv 0 i den första cellen på bandet; cykelstart simulera nästa steg för den givna Turing-maskinen vid den givna ingången; om Turing-maskinen har stannat, skriv 1 till den första cellen på bandet och bryt slingan ; slutet av slingan slutet av programmetSådana beräkningar, utöver förmågan hos en Turing-maskin, kallas hypercomputing .
Det är värt att notera att stoppproblemet för själva Zeno-maskinen inte kan lösas på Zeno-maskinen (Potgieter, 2006).