Re: What is the Result from Invoking this Halt Function?

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

Date: Tue, 17 Aug 2004 01:40:42 GMT

"Marc Goodman" <marc.goodman@comcast.net> wrote in message news:LgaUc.136186$8_6.113311@attbi_s04...
> stephen@nomail.com wrote:
> > In comp.theory Marc Goodman <marc.goodman@comcast.net> wrote:
> > : Will Twentyman wrote:
> > :> No. He means call your halt analyzer H, and find a new TM called K,
> > :> where they perform the same processing but K always returns a result in
> > :> a "useful" way. Computationally equivalent does not mean identical.
> >
> > : You need to prove that changing the return protocol doesn't change
> > : the calculation. I've seen this statement many times in this thread,
> > : but no one has offered a proof that shows it's true in all cases.
> >
> > If you removed function calls, return statements and the reference
> > operator from C/C++ it would still be Turing complete, and any
> > calculation that could be accomplished in normal C/C++ could be accomplished
> > in this restricted version of C/C++, and vice versa. If there are no
> > function calls or return statements there is no need to worry about
> > whether or not the return protocol changes the calculation.
> >
> > In
> > : that sense, no one has effectively disputed that the existence of H
> > : does not entail the existence of K and Peter is correct. On the
> > : contrary, Peter and others have offered at least two methods whereby
> > : H _does_not_ entail K: 1). in a C program that accesses memory directly
> > : to "look up" it's own binary encoding and conditionalizes behavior based
> > : on this
> >
> > You are not really writing a C program if you do this, because it
> > is not at all portable.
>
> It doesn't have to be portable. It only has to work in one case
> to demonstrate that it's possible. If it's possible, then this
> particular basis for refuting Peter's disproof is invalid.
>
> You are writing a C program for a particular
> > architecture, which should be totally irrelevant to the Halting problem
> > unless you believe that certain architectures are computationally
> > more powerful than others.
>
> I know I can write this on one machine for one programming language.
> Either that means that it can be written _or_simulated_ on all
> machines in all programming languages, or it means that some
> machines are more "powerful" than the Church Turing thesis
> would allow. I believe the former. Which do you believe?
>
> > : the TM can query the UTM about its state transition table.
> >
> > How? A TM can move its head, write a character, and/or change
> > state. There is no 'query the UTM' operation.
>
> Once again, it can be simulated. You can have a UTM with a
> static state transition table that simulates an entire computer
> with execution environment running a program, all on the UTM's
> tape. If it's possible in one instance, this particular basis
> for refuting Peter's claim is invalid.

Thanks again Marc. Finally its not me alone against everyone else.

> > : It's time to either _prove_ this is correct or put this particular
> > : line of reasoning to bed.
> >
> > It is only a problem if you are not specific about what your
> > computational model is. In the TM case, or the standardized C/C++/Java
> > case, it is trivially true.
>
> Unless your TM is a simulator that simulates an entire computer
> with its execution environment and running program.
>
> A TM cannot query its state table,
> > and has no return values anyway. There is no standardized way
> > for C to query its own code, and the semantics of return says that
> > the value is not changed.
> >
> > Stephen
>