On Thursday, November 1, 2018 at 12:31:13 PM UTC-5, John Clark wrote: > > On Wed, Oct 31, 2018 at 3:14 PM Philip Thrift <cloud...@gmail.com > <javascript:>> wrote: > > 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.* >> > > You can assume anything you like and you can define a dragon as a fire > breathing flying reptile if you like, but definitions don't cause something > to suddenly come into existence. > > > *The following ATM can solve the halting problem of an arbitrarily >> given TM T and input w in finite time: * >> > > The creator of this ATM made a crucial assumption namely "we assume that > steps are in some sense identical except for the time taken for their > execution". To me that is equivalent to saying at the end of step 3 in a > mathematical proof just before going to step 4 "at this point we assume a > miracle occurs". But there is a even more fundamental problem, solving the > Halting Problem is logically contradictory. > > If the ATM can solve the Halting problem then if I feed in any problem it > can tell me if it halts or not. Let's say the ATM has 2 slots for input and > one slot for output, if I feed in the circuit logic design blueprints of > any computer into one slot the ATM can simulate that computer, and if I > feed in program data into the other slot that ATM will output either > "Halt" meaning the simulated machine operating on that data will stop or > the ATM will output "not halt" meaning the simulated machine operating > on that data will not stop. > > I will now make a new machine called X, it has 3 parts to it. The first > part of X is just a Xerox copy machine, feed in one program and it outputs > 2 identical programs. The second part of X is the ATM and it receives the 2 > programs as input from the Xerox machine's outputs, and the ATM then > outputs either "halt" or "not halt". The third and last part of X is a very > simple machine called the negator, it receives as input the output of the > ATM and if the input to the negator is "Halt" the negator will go into a > infinite loop and if the input is "not halt" the negator will print "halt" > and then stop. > > Now lets draw the blueprint circuit design of the entire X machine that > fully defines it, then make 2 copies of it and feed it into the ATM; so the > ATM is now trying to figure out if the X machine will halt if it is fed its > own blueprint as data. If the ATM says "halt" the X machine will not halt > and the ATM was wrong. If the ATM says "not halt" the X machine will > halt and the ATM was wrong again. > > Therefore the ATM can not logically exist. > > John K Clark >
Zeno machines are just infinite-time Turing machines whose theory has been developed by @JDHamkins <https://twitter.com/JDHamkins> and others. http://jdh.hamkins.org/ittms/ *The Power of Infinite Time Machines How powerful are these machines? * *Perhaps the first thing to notice is that the halting problem for Turing machines is infinite time decidable. This is true because with an infinite time Turing machine one can simulate an ordinary Turing machine computation. Either the simulation halts in finitely many steps, or else after ω many steps the machine reaches the limit state, and so by giving the output Yes or No, respectively, in these two situations, the halting problem is solved. Thus infinite time Turing machines are more powerful than ordinary Turing machines: they can decide sets which are undecidable by Turing machines. The next theorem greatly improves on this.* Theorem 2.1 The truth of any arithmetic statement is infinite time decidable. All of this is standard in computability theory: There are levels of Turing machines starting at level 0 where a TM at level n+1 solves the haling problem of level n. How "real" you think this is depends on whether you are a *Platonist *or a* fictionalist*. For it to be "real" in the natural world would require a physical hypercomputaional substrate, like a hypothetical black hole (relativistic) computer. - 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.
