Re: Attempt to Refute the Halting Problem's Refutation

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 08/13/04 

Date: Thu, 12 Aug 2004 23:59:41 GMT

<newstome@comcast.net> wrote in message news:cXASc.241712$%_6.157961@attbi_s01...
> OK, before we get started with the meat of this, we need to agree on
> some definitions, so here we go:
>
> Definition: The "Halting Problem" is a problem which takes two inputs
> (machine,input), where "machine" is a description of a Turing Machine
> and "input" is the input to be supplied to that machine, and you are
> asked if "machine" halts when run with input "input". A program
> "correctly solves the halting problem" if (and only if) it correctly
> determines the answer to this question for all inputs (all
> <machine,input> pairs).
>
> Notice that I simply said "determines the answer" so that we're not
> restricted on how it reports (or doesn't report) the answer.
>
> I believe you've acknowledged this as what Turing proved before, so
> let me know if we can use this as a fact: No Turing Machine that
> returns its answer can correctly solve the halting problem.
>
> If you don't want to take that as proven fact, that's fine, we can
> work around it, but let me know.
>
> Your turn: Let me know if that definition is OK, and whether or not
> to accept the result about machines that return the answer.
>
> --
>
> That's News To Me!
> newstome@comcast.net

Let's try to work directly with Turing's own material, like Parr has suggested.

Halting Problem according to Alan Turing:
The problem of finding out whether a given number is the D.N of a
circle-free machine,

Translation: (The problem of finding out whether a given Turing Machine
Description specifies a Turing Machine that fails to Halt).

The above translation was based on pages 5, 12 and 18 of the following
http://www.abelard.org/turpap2/tp2-ie.asp

Turing's words continued:
and we have no general process for doing this in a finite number of steps.
In fact, by applying the diagonal process argument correctly, we can show
that there cannot be any such general solution.

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: What is the Result from Invoking this Halt Function?
    ... Each and every case of any statement meaning essentially the same ... Definition of the Halting Problem ... There does not exist a Turing Machine that can correctly determine ... and we have no general process for doing this ...
    (comp.theory)