ماشین زنون

در ریاضیات و علوم کامپیوتر ماشین زنون (تورینگ ماشین شتابیافته) که یک مدل محاسباتی فرضی وابسته به تورینگ ماشین هاست که امکان انجام تعداد بیشمار مرحلهٔ الگوریتم را در یک زمان محدود می‌دهد. این ماشین‌ها به عتوان یکی از مهم‌ترین مدل‌های محاسباتی شناخته می‌شود. به شکل صوری‌تر یک ماشین زنون ماشین تورینگی است که n مرحله از الگوریتم را در n واحد زمانی انجام می‌دهد؛ بنابراین اولین مرحله ۰٫۵ واحد زمانی دومین ۰٫۲۵ واحد زمانی و سومین مرحله ۰٫۱۲۵ و به همین صورت. درنتیجه بعد از یک واحد زمانی، بینهایت (بینهایت شمارا) مرحله انجام خواهد شد.

ایدهٔ ماشین‌های زنون برای اولین بار توسط هرمن ویل مطرح شد در سال ۱۹۲۷ و ان را به نام فیلسوف یونان باستان زنون نام نهادند. ماشین‌های زنون نقش حیاتی را در برخی تئوری‌ها ایفا می‌کند تئوری‌های مانند نقطه امگا، مطرح شده توسط فیزیکدان فرانک جی تیپلر. تنها در صورتی می‌توانند برقرار باشند که ماشین‌های زنون قابل تعریف باشند

ماشین زنون و محاسبه‌پذیری

ماشین‌های زنون این اجازه را به ما می‌دهند که توابع زیادی را که توسط تورینگ ماشین‌ها قابل محاسبه نیستند را محاسبه کنیم با توجه به شبه الگوریتم زیر:

begin program
write 0 on the first position of the output tape;
begin loop
 simulate 1 successive step of the given Turing machine
on the given input;
 if the Turing machine has halted, then write 1 on the first position of the output tape and break
out of loop;
end loop
end program

محاسباتی از این نوع که فراتر از محدودیت‌های تورینگ ماشین است فرا محاسبات نامیده می‌شوند. قابل ذکر است که مسالهٔ توقف برای ماشین‌های زنو توسط ماشین‌های زنو قابل حل نمی‌باشد.

منابع

Wikipedia contributors, "Zeno machine," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Zeno_machine&oldid=633464665 (accessed January 24, 2015).