Re: Attempt to Refute the Halting Problem's Refutation

newstome_at_comcast.net
Date: 08/13/04 

Date: Fri, 13 Aug 2004 02:09:07 GMT

In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>
> <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.

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

Actually, I'd rather stick with *your* words, since this is showing
how *you* are wrong. Is that OK?

> 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.
>
>
> 

-- 
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. ...
    (sci.logic)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... > restricted on how it reports the answer. ... > returns its answer can correctly solve the halting problem. ... (The problem of finding out whether a given Turing Machine ... 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. ... (The problem of finding out whether a given Turing Machine ... and we have no general process for doing this in a finite number of steps. ...
    (sci.logic)
  • Attempt to Refute the Halting Problems Refutation
    ... The "Halting Problem" is a problem which takes two inputs ... , where "machine" is a description of a Turing Machine ... restricted on how it reports the answer. ... If you don't want to take that as proven fact, that's fine, we can ...
    (comp.theory)
  • Attempt to Refute the Halting Problems Refutation
    ... The "Halting Problem" is a problem which takes two inputs ... , where "machine" is a description of a Turing Machine ... restricted on how it reports the answer. ... If you don't want to take that as proven fact, that's fine, we can ...
    (sci.logic)