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 <cloud...@gmail.com > <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 everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
