Attempt to Refute the Halting Problem's Refutation

newstome_at_comcast.net
Date: 08/12/04 

Date: Thu, 12 Aug 2004 02:51:52 GMT

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

Relevant Pages

  • Re: Attempt to Refute the Halting Problems Refutation
    ... >> restricted on how it reports the answer. ... >> 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 ... > and we have no general process for doing this in a finite number of steps. ...
    (comp.theory)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... >> restricted on how it reports the answer. ... >> 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 ... > and we have no general process for doing this in a finite number of steps. ...
    (sci.logic)
  • 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)