ماشین زنون

در ریاضیت و علوم کامپیوتر ماشین زنو (تورینگ ماشین شتابیافته) که یک مدل محاسباتی فرضی وابسته به تورینگ ماشین هاست که امکان انجام تعداد بیشمار مرحلهٔ الگوریتم را در یک زمان محدود می دهد. این ماشین ها به عتوان یکی از مهم ترین مدل های محاسباتی شناخته می شود.به شکل رسمی تر یک ماشین زنو یک تورینگ ماشینی است که n مرحله از الگوریتم را در n2 واحد زمانی انجام می دهد؛ بنابراین اولین مرحله نیم واحد زمانی دومین ۲۵ واحد زمانی و سومین مرحله ۱۲۵ و به همین صورت.پس بعد از یک واحد زمانی یک مجموعه شمارا از مراحل انجام خواهد شد.
Wikipedia contributors, "Zeno machine," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Zeno_machine&oldid=633464665 (accessed January 24, 2015).
ایده ماشین های زنا برای اولین بار توسط هرمن ویل مطرح شد در سال ۱۹۲۷ و ان را به نام فیلسوف یونان باستان زنو نام نهادند. ماشین های زنو نقش حیاتی را در برخی تئوری ها ایفا می کند تئوری های مانند نقطه امگا، مطرح شده توسط فیزیکدان فرانک جی تیپلر. تنها در صورتی می توانند برقرار باشند که ماشین های زنو قابل تعریف باشند
ماشین های زنو این اجازه را به ما می دهند که توابع زیادی را که توسط تورینگ ماشین ها قابل محاسبه نیستند را محاسبه کنیم با توجه به شبه الگوریتم زیر:
begin programwrite 0 on the first position of the output tape;begin loop simulate 1 successive step of the given Turing machineon the given input; if the Turing machine has halted, then write 1 on the first position of the output tape and breakout of loop;end loopend program محاسباتی از این نوع که فراتر از محدودیت های تورینگ ماشین است فرا محاسبات نامیده می شوند. قابل ذکر است که مسالهٔ توقف برای ماشین های زنو توسط ماشین های زنو قابل حل نمی باشد.