Re: Yet another Attempt at Disproving the Halting Problem

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

Date: 14 Aug 2004 06:40:33 -0700

>parr\(*> says...

>| Whatever. Do you agree that Turing proved that there is no
>| program H(x,y) which for any pair of inputs x and y, *always*
>| returns 1 if x is the code for a computer of one argument that
>| halts on input y, and *always* returns 0 otherwise?

>He's nowhere where ready to understand Turing's paper. He hasn't a
>clue what Un(m) means, and particularly the significance of the 'n'
>in that expression.

>And nor have you. If you did, you'd know that in his paper, Turing
>also proved that for certain, limited, machines, the halting problem
>could be solved.

Yes, if you have a limited class of functions that are not
Turing-complete, then sometimes the halting problem can solved
for programs in that class. So? The interesting issue is whether
it is solvable for a Turing-complete set of programs.

Also, I don't personally think that there is anything special
about Turing machines. It was the first example of a Turing-complete
set of programs, and they are an especially simple type of machine,
but the issues involved in the halting problem arise in almost
the same way no matter what model of machine you are using, as
long as it's Turing-complete.

Actually, diagonalization is more general than the halting problem.
As you say, the halting problem is solvable for some classes of
machines. On the other hand, *no* class of machines can compute
its own diagonal:

    diag(x) : If x is the code for a program of one argument that
              halts on input x, and the result of that computation
              is 0, then return 1. Otherwise, return 0.

No matter what class of programs you are talking about (as long
as you can make sense of the phrases "is a code for", "takes one
argument", "returns a result", "halts on input x"), diag(x) is a
well-defined mathematical function that cannot be computed by any
program in that class. For a Turing-complete class of programs,
the non-existence of a program (in that class) computing diag(x)
implies the nonexistence of a program (in that class) solving the
halting problem for that class. 

--
Daryl McCullough
Ithaca, NY

Relevant Pages