On Wednesday, October 31, 2018 at 11:13:17 AM UTC-5, John Clark wrote: > > > > On Tue, Oct 30, 2018 at 1:30 PM Philip Thrift <[email protected] > <javascript:>> wrote: > > > *More formally, a **Zeno machine is a Turing machine that....* > > > The rules of Zeno's machine never change so if its a Turing Machine it's > must be a one state Turing Machine, the very simplest type. But there are > only 64 different one state Turing Machines and none of them are Zeno's > machine. So it's not a Turing Machine, Zeno's machine is just not powerful > enough to be even the simplest type of Turing Machine. > > John K Clark >
A Zeno Machine (ZM) - or Accelerated Turing Machine (ATM) - can solve the Turing Machine (TM)* halting problem*: >From https://www.cs.auckland.ac.nz/~cristian/talks/selected/BeamerATM.pdf An accelerated Turing machine (sometimes called *Zeno machine*) is a Turing machine that takes 2^−n units of time (say seconds) to perform its nth step; we assume that steps are in some sense identical except for the time taken for their execution. The following ATM can solve the halting problem of an arbitrarily given TM T and input w in finite time: begin program write 0 on the first position of the output tape; set i = 1; begin loop simulate the first i steps of T on w; if T(w) has halted, then write 1 on the first position of the output tape; i = i + 1; end loop end program - pt -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
