A Zeno machine of order 1 is a Turing machine that uses half the time it ran its $(n-1)$th step to run its nth step, hence can run infinite steps in just 2 seconds. This is called one step of order 1.

A Zeno machine of order $n$ is a Zeno machine of order $(n-1)$ that runs infinite steps (of order $n-1$) in $2^n$ seconds first step (of order $n$), but in $2^{n-1}$ seconds second step, and in $2^{n-m}$ seconds the mth step.

So, exactly what type of formal language is a Zeno machine of order $n$ capable of recognizing?

  • 1
    $\begingroup$ You haven't defined when a Zeno machine accepts an input. $\endgroup$ – Yuval Filmus Aug 7 '13 at 19:02
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Zeno_machine $\endgroup$ – Kaveh Aug 8 '13 at 4:30
  • $\begingroup$ AFAIK, anything that a Turing machine would recognize in infinite time. $\endgroup$ – Trylks Aug 8 '13 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.