Re: Yet another Attempt at Disproving the Halting Problem

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 08/13/04 

Date: 12 Aug 2004 19:47:14 -0700

Peter Olcott says...

>Yup it is completely obvious to anyone whom has not thought it through
>at all.

You haven't thought through *anything* at all, Peter. You are spinning
your wheels trying to make a pink elephant by turning off the lights.
Turing's counterexample isn't what *caused* the alleged Halt function
to be incorrect; it is the *evidence* that it incorrect. Destroying
the evidence doesn't make it work any better.

Here's an argument for the impossibility of solving the halting problem
that doesn't in any way rely on one program calling another program.

Pick a programming language (say C). Then we define the following
*mathematical* function on strings (*not* a program---it's just a
function):

    diag(x): If x is the code for a program of one string argument
           that is functional (that is, it always behaves in the same way
           for the same inputs), and x is a legal input to that program,
           and that program halts on input x, and the result of running
           that program on input x is nonzero, then diag(x) = 0.
           Otherwise, diag(x) = 1.

Note: When I say "results" I don't care whether the result is a return
value, or something printed to the screen, or something written to a
file, or something said out loud using a voice synthesizer. However the
program gives its results, if the result of running program x on input
x is nonzero, then diag(x) = 0. Otherwise, diag(x) = 1.

   Claim: There is no computer program Q such that for any input x
   will produce the result diag(x).

   Proof: Let Q(x) be any computer program that takes one string argument,
   and let #Q be the code of Q. Then Q(#Q) cannot produce the result
   diag(#Q). Either diag(#Q) is 0 (in which case Q(#Q) is something nonzero),
   or diag(#Q) is 1 (in which case, Q(#Q) either doesn't halt, or produces
   the result 0).

So the conclusion is that there exists a mathematical function that
is not computable by any computer program. Let me remind you that
diag is *not* a computer program. It doesn't actually *call* any
computer programs. It's just that diag(x) is defined in terms of
what *would* happen if you called program x on input x. So it doesn't
help to say that some programs behave differently depending on the
context in which they are called. That doesn't matter.

So the function diag(x) is not computable. Now here's a fact about
diag(x):

    Claim: If there were were a program H(x,y) that solved the halting
    problem, then diag(x) would be computable by a sufficiently patient
    and careful human being.

    Proof: To compute diag(x), just simulate (on paper) H(x,x). If
    the result is 1, then you know that x is a code for a program
    that halts on input x. In that case, you simulate the operation
    of program x running on input x. If the result is 0, then you
    know that diag(x) = 1, and if the result is nonzero, then you
    know that diag(x) = 0.

    If the result of simulating H(x,x) is 0, then you know that x
    is not a code for a program that halts on input x. In that case,
    you know that diag(x) = 1.

So a human being equipped with sufficient amounts of paper could
compute diag(x). By Church's thesis, any deterministic mechanical
algorithm that can be carried out by a human being using pencil
and paper is computable by a computer program. Therefore:

    Lemma: If H(x,y) were computable, then diag(x) would be
    computable.

    Conclusion: Since diag(x) is not computable, then neither is H(x,y). 

--
Daryl McCullough
Ithaca, NY

Relevant Pages