Re: Alan Turing's Halting Problem is incorrectly formed (PART-TWO)

From: Dave Seaman (dseaman_at_no.such.host)
Date: 06/25/04

  • Next message: Mike Terry: "Re: Cantor's wrong! (doubt it)" 
    Date: Fri, 25 Jun 2004 13:06:10 +0000 (UTC)

    On 25 Jun 2004 05:18:31 -0700, Eray Ozkural exa wrote:

    > HALTING PROBLEM: Let U be a universal computer. Let w be a program
    > string and x be an input string. U(w,x) denotes the computation of
    > program w with input x. The computation U(w,x) is said to be halting
    > if it terminates and outputs a string y=U(w,x) after a finite number
    > of steps. Is there a program p such that U(p, [w,x])=1 if U(w,x) halts
    > and U(p, [w,x])=0 if U(w,x) does not halt for all w and x, where [w,x]
    > denotes the encoding of pair (w,x)?

    > This is a legitimate question, although the proof seems too easy to
    > believe. If we didn't know the proofs, then we would be considering
    > that it might be possible for such p to exist, since it is possible
    > for a program to examine the code for input program w and data x, and
    > make a decision. Unfortunately, it turns out that any p can decide the
    > halting problem for only a finite number of input programs, and not
    > for all inputs as the problem asks.

    I can think of at least two counterexamples to your claim; the program
    p_1 such that U(p_1, [w,x]) always returns 1, and the program p_0
    given by U(p_0, [w,x]) = 0.

    Much as a stopped clock is right infinitely often (twice a day, forever),
    each of those programs correctly decides the halting problem for
    infinitely many inputs. 

    -- 
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
  • Next message: Mike Terry: "Re: Cantor's wrong! (doubt it)"

    Relevant Pages