<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2013-08-07T19:02:49.373Z
You haven't defined when a Zeno machine accepts an input.
Yuval Filmus
CC BY-SA 3.0
2013-08-08T04:30:09.590Z
http://en.wikipedia.org/wiki/Zeno_machine
Kaveh
CC BY-SA 3.0
2013-08-08T15:04:58.473Z
AFAIK, anything that a Turing machine would recognize in infinite time.
Trylks
<hypercomputation>
What language does Zeno machines recognize?
user2249675
# What language does Zeno machines recognize?

(Asked by: username_0 on 2013-08-07)

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?

**Tags:** hypercomputation
> **Comments:**
> **username_1**: You haven't defined when a Zeno machine accepts an input.  
> **username_2**: http://en.wikipedia.org/wiki/Zeno_machine  
> **username_3**: AFAIK, anything that a Turing machine would recognize in infinite time.  

---

## 0 answers

