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

From: Marc Goodman (marc.goodman_at_comcast.net)
Date: 08/17/04 

Date: Mon, 16 Aug 2004 22:09:47 GMT

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.

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

Relevant Pages

  • Re: What is the Result from Invoking this Halt Function?
    ... > whether or not the return protocol changes the calculation. ... machines in all programming languages, ... There is no 'query the UTM' operation. ...
    (sci.logic)
  • Re: Does DateDiff Have A Bug
    ... Now I just use the results from the query and everything works better than ... MemberID FirstName LastName EntryDate DaysRemaining ... calculated field within it's calculation) would look like; ... if there are zero days left which in ...
    (microsoft.public.access.formscoding)
  • Re: Does DateDiff Have A Bug
    ... I changed the form (Members) RecordSource back to my Main ... Now I just use the results from the query and everything works better than ... MemberID FirstName LastName EntryDate DaysRemaining ... calculated field within it's calculation) would look like; ...
    (microsoft.public.access.formscoding)
  • Re: QUERY STRUGG
    ... It appears that you want to plot a graph based on the results of a Query that is not working correctly. ... protocol weekid week signed screen fail lfu ... 2- showing in the linear graphic filtering by protocol ... There will be 2 lines for each PROTOID, one that shows originated numbers and one the shows acumulative. ...
    (microsoft.public.access.queries)
  • Re: Does DateDiff Have A Bug
    ... Now you would go to Queries/Create query in Design View, ... MemberID FirstName LastName EntryDate DaysRemaining ... calculated field within it's calculation) would look like; ... I'm trying to write the result of lngDays when it reaches zero days ...
    (microsoft.public.access.formscoding)