Re: Peter Olcott's Source of Confusion

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 07/05/04 

Date: 5 Jul 2004 05:08:20 -0700

Peter Olcott says...

>"Daryl McCullough" <daryl@atc-nycorp.com> wrote

>> Solving the halting problem isn't analytically impossible---it is
>> only analytically impossible for a *computer* program to solve it.
>> It can be solved with what is sometimes called a "Zeno machine",
>> which is like a Turing machine except that it performs its first
>> computation step in 1 second, its second step in 1/2 second, its
>> third step in 1/4 second, etc. So it performs infinitely many
>> steps in 2 seconds. Such a program can exhaustively search to
>> see if a Turing machine M halts on input x.
>
>Although the concept itself does not fall utterly apart, that it
>would solve the Halting Problem sure seems like pure malarkey.

Well, it's not. Such a machine can answer any question in the so-called
"arithmetic hierarchy", which includes the halting problem.

>How long it takes to perform a step is utterly irrelevant to solving
>the Halting Problem (as long as it is less than eternity).

Processing speed is irrelevant as long as there is some lower bound
on the time it takes for any computation step, and some upper bound.
If there is no lower bound on processing speed, then there is no
upper bound on how many steps can be done in 2 seconds.

Although the unlimited halting problem "Does P ever halt on input q?"
is unsolvable, it is easy enough to write a solution to the
step-limited halting problem "Does P halt on input q in fewer than n
steps?" There *is* a program that solves this problem:

   H(x,y,n) = true
   if x is a code for a program that halts on input y in fewer than n steps
   H(x,y,n) = false, otherwise

So, the Zeno machine can, for any x and y, determine whether x is
a program that ever halts on input y in the following way:

    1. First check H(x,y,0) (Do this check in 1 second) if it is true,
    return true.

    2. Otherwise, check H(x,y,1) (Do this check in 1/2 second). If true,
    return true.

    3. Otherwise, check H(x,y,2) (Do this check in 1/4 second). If true,
    return true.

    4. etc.
    (In general, spend 2^{-n} seconds to check if H(x,y,n)=true. If so,
    return true.)

After 2 seconds, if the Zeno machine does *not* return true, then that
means that there is no n such that H(x,y,n) = true. That means that x
never halts on input n. 

--
Daryl McCullough
Ithaca, NY

Relevant Pages

  • Re: Partial recursive functions and minimization
    ... Suppose that T is a Turing Machine. ... Then G is partial recursive if and only if the halting problem for T ... whether or not T halts on x. Stated this way, ... since it contradicts the undecidability of the Halting Problem. ...
    (sci.math)
  • Re: Gödel, Turing, and Cantor
    ... >1) Gödel's incompleteness theorem ... >machine for which the halting problem is undecidable. ... Turing machine #n [in an appropriate ... finitely many steps that the Turing machine performs until it halts]. ...
    (sci.math)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... The Halting Problem does not ... It most definitely does say that a Turing Machine ... X halts, for all X, where X is a Turing Machine and input string." ...
    (comp.lang.cpp)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... The Halting Problem does not ... It most definitely does say that a Turing Machine ... X halts, for all X, where X is a Turing Machine and input string." ...
    (sci.logic)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... The Halting Problem does not ... It most definitely does say that a Turing Machine ... X halts, for all X, where X is a Turing Machine and input string." ...
    (comp.theory)