Re: Can you find anything wrong with this solution to the Halting Problem?

From: Sander Bruggink (bruggink.at.phil.uu.nl_at_no.spam.please)
Date: 07/16/04 

Date: Fri, 16 Jul 2004 11:41:47 +0200

Peter Olcott wrote:
[I wrote:]
>>No, it is *the* definition. Turing's proof is about *Turing machines*,
>>or more generally *Turing-complete languages*.
>
> Even my other adversary (the one that is pretending to be
> G Frege) disagrees with this staminate of yours.

I seem to have missed the post where he disagrees with this. Please
provide a link. (It is of course possible to ask whether a halting
function exists for different classes of functions, but *Turing* asked
that question for Turing machines.)

> This seems
> to show a fundamental lack of understanding on your part
> about the nature of a Turing Machine.

Exactly what is the nature of a Turing Machine, according to you, then?
I'm particularly very interested in how the protected memory, non-pseudo
RNG, and screen are formulated.

> It completely ignores
> the Church-Turing thesis.

Do you even know what the Church-Turing thesis is? Which of the
following do you think it resembles more: a *definition* or a *theorem*?

>>Yes you did. Your WillHalt function is allowed to somehow call a
>>non-pseudo random number generator,
>
> This has nothing to do with different languages, its merely input from a serial
> port.

Whatever. This doesn't change my point at all.

>>but the counter example isn't
>>allowed to do that. The counter example may not access all features. (It
>>is apperantly written in a language which restricts the use of such a RNG).
>
> No the definition of the original problem is what prohibits RNG.

Indeed. And in the definition of the original problem the use of
non-pseudo RNG (and protected memory, too) by the halting function are
also prohibited. This is because the halting problem is only interesting
if the halting function has access to the same features as the programs
of which it has to decide whether they halt.

You have really two options:

(1) Disallow non-pseudo RNG for *both* the halting function and the
counter example. (This is the preferred option.) This makes your halting
function invalid.

(2) Allow non-pseudo RNG for *both* the halting function and the counter
example. Note, that the language is now no longer Turing-complete, but
*more powerful*. So we are no longer talking about the *original*
halting problem, but about a *more general* one.
     The consequence of choosing this option, however, is that you have
to allow the following program as a counter example:

function HaltsOrNot() {
   if (random() > .5) then while (true);
                      else return;
}

Your WillHalt function fails to determine whether or not this program
halts in about 50% of the cases.

>>For this reason, if your proof would work (which, as G. Frege has
>>sufficiently shown, it doesn't), then it would only show something which
>>is already completely obvious.

groente
-- Sander