Re: The proof that I was referring to is on the website

From: Rick Decker (rdecker_at_hamilton.edu)
Date: 08/05/04 

Date: Thu, 05 Aug 2004 09:43:05 -0400

Peter Olcott wrote:

> "Rick Decker" <rdecker@hamilton.edu> wrote in message news:4110E973.6010605@hamilton.edu...

<snip>

>>
>>It appears that you might be assuming that there could
>>be a difference between the results of the invocations
>>of halts in
>>
>> cout << halts(perverse, perverse)
>>
>>and
>>
>> if (halts(perverse, perverse))
>>
>>when we run perverse on its own description.
>>If that could happen, then your argument might indeed
>>be correct.
>>
>
> It is not a mere assumption, its a fact, and it forms the fundamental
> basis for my latest proof.
>

It's not a fact. As I said below, that's not the way
*any* TM works. Given a TM M and an input string w,
M, when started on w, will always act in exactly the
same way, regardless of the context.

 
>
>>However, that's not the way the TM halts( , )
>>works. In fact, it's not the way any TM works. You can
>>assume that the result returned by halts does indeed
>>differ for the same inputs in different contexts, but
>>then halts is not a TM and you're still sunk.
>>
>
> Church-Turing thesis
> Any computation that can be carried out by mechanical means
> can be performed by some Turing Machine.
>
> This seems to include just about everything right?
> It would certainly include what I have proposed.
>
Certainly not.

At any rate, I'm pleased to have finally discovered where
your misconception lies. You've shown that the standard
proof of the undecidability of the halting problem may
be invalid when applied to a class of abstract machines
with properties different from Turing Machines.

Regards,

Rick

Relevant Pages

  • Re: Contradiction or paradox
    ... and ~_is_ a wff by that definition. ... ~LTand then halts. ... The rest of the line is CBL command write with argument ... YES"Turing Machine a halts yes on input b." ...
    (sci.logic)
  • Re: Rados Sigma and the Halting Problem for Programs
    ... AD> computer language that does not contrive a logic paradox ... Halting Theorem may be proven without recourse to reductio ... computation halts, and is bottom, i.e. _|_ if the computation diverges ... Assume that from a Turing Machine M we can construct a Turing Machine ...
    (comp.theory)
  • Re: Rados Sigma and the Halting Problem for Programs
    ... AD> computer language that does not contrive a logic paradox ... Halting Theorem may be proven without recourse to reductio ... computation halts, and is bottom, i.e. _|_ if the computation diverges ... Assume that from a Turing Machine M we can construct a Turing Machine ...
    (sci.math)
  • Re: Rados Sigma and the Halting Problem for Programs
    ... AD> computer language that does not contrive a logic paradox ... Halting Theorem may be proven without recourse to reductio ... computation halts, and is bottom, i.e. _|_ if the computation diverges ... Assume that from a Turing Machine M we can construct a Turing Machine ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... same way, regardless of the context. ... >>assume that the result returned by halts does indeed ... > can be performed by some Turing Machine. ...
    (comp.theory)