Talk:Zeno machine

Halting Problem

"(The halting problem for Zeno machines cannot be solved using a Zeno machine, however)."

Is this true? Don't all Zeno machines halt, making the halting function trivially f(T, i) = 1 for any Zeno machine T with any input i? --NoizHed 01:06, 20 March 2006 (UTC)

If you accept the logical possibility of Zeno machines, that would seem to be the logical conclusion, yes. But as noted in the article, accepting the possibility of Zeno machines leads to some serious problems: take the turing machine that simply keeps moving left, no matter what symbol it reads. Clearly, this machine will never halt. But according to the Zeno machines enthusiasts, if you take the accelerated version of this machine, then it should stop after some finite amount of time, having taken infinitely many steps. Indeed, all Zeno machines should halt according to their specifications. Personally, that sounds baloney to me. By definition of infinity, taking infinitely many steps means that you will never finish going through those steps, whether you accelerate this or not. Indeed, I would say we have reached a logical contradiction here, just as in Zeno's paradox. Therefore, I declare Zeno machines to be logically impossible (note: not just physically impossible, but logically impossible). —Preceding unsigned comment added by 72.226.66.230 (talk) 20:07, 3 July 2008 (UTC)

Except that the Zeno machine accelerates infinitely. So you're insisting that infinity / infinity = infinity. Nope.

Well, that is _one_ answer, depending on how you define division and infinity. Under the simplest definitions, any positive number n, finite or infinite, satisfies the equation n x infinity = infinity. So infinity is a valid answer, but so is 1, or 23.42. So, looked at it that way, the answer isn't "no"--there's not enough information in the problem to provide an answer.

But really, there is an answer. The problem doesn't come down to "what's infinity over infinity." The rate of acceleration is proportional to the number of steps. If it takes x steps to halt, it takes 1-1/2^x minutes to halt. The limit of this time as x approaches infinity is 1. So, a Zeno machine always halts.

That doesn't prove that a Zeno machine is logically possible--just that any Zeno machines that are logically possible (of which there might be none) halt. That's enough to make the halting functional trivial. --75.36.137.180 (talk) 16:52, 16 February 2009 (UTC)

OK, so what are you saying?!? You seem to be contradicting yourself. Anyway, in the end you apparently agree that, if the concept of a Zeno machine holds any water, all Zeno machines should halt. But clearly that leads to trouble, as the examples given earlier demonstrate. Pure logic thus derives a contradiction from the possibility of Zeno machines. In other words, Zeno machines are impossible. And no assumptions about infinity / infinity need to be made in order to derive that contradiction. —Preceding unsigned comment added by 67.244.167.93 (talk) 21:16, 15 March 2009 (UTC)

Think about it this way: We want to read the output of computation from the tape. Suppose we read it from the first cell. In one computation a Zeno machine can write to the cell infinitely many times (e.g. zero and one alternatively). What is the output after computation is "finished"? It may undefined. We only get an output if the first cell stabilises (e.g. the machine keeps writing ones in the first cell from some point). So I think what here is meant by "The halting problem for Zeno machines" is this: Given a Zeno machine Z and input i, does Z with input i give an output? Hope that helps somebody. Czego szukasz (talk) 13:44, 29 November 2010 (UTC)

"(The halting problem for Zeno machines cannot be solved using a Zeno machine, however)."

of course its true it says on the paper. have you actually read the paper you cite? —Preceding unsigned comment added by 138.250.193.98 (talk) 08:40, 6 November 2009 (UTC)

Abstract

This paper reviews the Church–Turing Thesis (or rather, theses) with reference to their origin and application and considers some models of “hypercomputation”, concentrating on perhaps the most straight-forward option: Zeno machines (Turing machines with accelerating clock). The halting problem is briefly discussed in a general context and the suggestion that it is an inevitable companion of any reasonable computational model is emphasised. It is suggested that claims to have “broken the Turing barrier” could be toned down and that the important and well-founded rôle of Turing computability in the mathematical sciences stands unchallenged. —Preceding unsigned comment added by 138.250.193.98 (talk) 08:45, 6 November 2009 (UTC)

I haven't read the paper, but my guess would be that a ZM is allowed to do \omega steps of computation, and then keep going; if it can do step number \omega, \omega+1, ..., then the halting question seems like it's probably sensible. Maybe someone can check the source and update the main article with a clarification. Joule36e5 (talk) 19:30, 6 August 2012 (UTC)

Computational power

A ZM can solve the TM-halting problem. So can a TM-Oracle, by definition. Does a ZM have equivalent computational power to a TM augmented with a TM-Oracle? Joule36e5 (talk) 19:40, 6 August 2012 (UTC)

I suspect it depends on how many limit ordinals the Zeno machine is allowed to reach. If the next limit ordinal is one we’ve decided should be forbidden, then we will just treat it like an ordinary Turing machine from then on (either it halts or it runs forever). Otherwise we let it reset itself (with lim sup) at the next limit ordinal.

If it is designed to only “cross infinity” once, it will have the same power as a TM with an TM Oracle. If it can do so twice (i.e, it can reach step ω·2, but not ω·3), it would have the same power as a TM augmented with an oracle for TM’s that are themselves augmented with TM oracles. Thus it would be even more powerful. See Turing jump, which is a closely related topic, as is hyperarithmetical theory.

This means that the Zeno machine can keep getting more and more powerful (in terms of Turing jumps), depending on how many limit ordinals it is allowed to access. If you wanted to, you could even let it cross over to ω·ω, by taking the lim sup of the lim sup states it attained at each ω·n (when n was finite). It at least makes sense logically even if it’s hard to visualize (and impossible for a physical machine to do).LonelyBoy2012 (talk) 04:27, 29 March 2024 (UTC)

What is the next step?

A Zeno machine can solve the halting problem for a Turing machine. What can solve the halting problem for a Zeno machine? -32ieww 10:04PM 11/20/2015 NY time 32ieww (talk) 03:04, 21 November 2015 (UTC)