5
$\begingroup$

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?

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.