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 14:59:13 +0200

Peter Olcott wrote:
[I wrote:]
>>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.
>
> That is simply not true.

Yes is it. I already presented to you, by means of a simple
example, why it is obvious (i.e. not interesting) that a
program in some language B, which has more features than
language A, could, in principle, decide the halting problem
for programs written in language A.

> The conclusion of the original problem was
> that it is completely impossible to always be able to correctly
> determine whether or not any other Turing Machine would halt,
> regardless of any possible means to do so.

No, the original theorem says that that is not possible
*for a Turing machine*. You can't change the theorem, but
keep the original proof, and then claim that the proof is
incorrect because it doesn't prove the changed theorem.

> The determination of
> this was only framed within the context of a Turing Machine because
> it was considered equivalent to every other possible computer.

When the theorem was proved, computers did not even exist.
Also, what motives Turing might have had to restrict his
proof to Turing machines is not relevant.

>
>>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.
>
> I see you have not looked at the updated version of my proof.

You know, I do have other things to do. I am not going to
check every minute whether or not your stupid page has
changed. You should indicate when you change your page, and
what the changes are.

> I don't even bother to mention the hardware RNG any more.
> http://home.att.net/~olcott/halts.html

You're right. It doesn't mention it anymore. You're still
using extra features, though, viz. "protected memory" and a
"screen". So my argument still stands.

To conclude, your "proof" is worthless on three accounts:
(1) Your method doesn't work.
If it would work,
(2) it would prove something completely obvious; and
(3) it would not refute Turing's proof.

groente
-- Sander

Relevant Pages

  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (sci.logic)
  • Re: Exploiting limitations of Turing machines in Turing tests?
    ... correctly answer _any_ halting problem question. ... You were proposing that there exists some finite set of special Turing ... able to successfully answer _all_ halting problem questions. ... It's a description of some Turing Machine, and some input, with the simple ...
    (comp.ai.philosophy)
  • Re: [PO] Re: Proving a negative is hard
    ... and for these conventions ... > Turing machines with the standard conventions for input/output ... > he agrees that there is no standard Turing Machine program ... > that solves the halting problem, ...
    (sci.logic)
  • Re: [PO] Re: Proving a negative is hard
    ... and for these conventions ... > Turing machines with the standard conventions for input/output ... > he agrees that there is no standard Turing Machine program ... > that solves the halting problem, ...
    (comp.theory)