Re: Can returning a value change the value itself (in the Halting Problem)

stephen_at_nomail.com
Date: 08/24/04 

Date: 24 Aug 2004 20:52:49 GMT

In comp.theory Marc Goodman <marc.goodman@comcast.net> wrote:
: stephen@nomail.com wrote:
:> In comp.theory Marc Goodman <marc.goodman@comcast.net> wrote:
:> : Martin Shobe wrote:
:> :> Of course the value changed. The *input* changed.
:>
:> : The context is a TM with access to its own state transition
:> : table that can calculate the check sum of its own state
:> : transition table. Do you finally see that even making
:> : a "trivial" change to such a TM can cause the result produced
:> : by such a TM to change? Or do we have to go through this
:> : line of argument three more times?
:>
:> : But, both
:> :> functions implement exactly the same, um, function.
:>
:> : You are free to call it "different input" if you want,
:> : but the fact remains that if you are talking about
:> : a TM with access to its own state transition table, the
:> : line between "input" and "process" has been blurred.
:> : To the extent that a seemingly local change to the
:> : TM can have a global change to the result produced by
:> : the TM.
:>
:> The point of a computational model is to compute mathematical functions.
:> A mathematical function has an input and an output. There is no
:> blurring, other than in your presentation. For your model where the program
:> can inspect itself you have to decide if the program is part of the input
:> or not.

: Yes, it is definitely part of the input.

In which case it is easy to write another program that computes
the same function. The example posted was such a program.
For any input, the two programs will produce the same output.

: If the program is not part of the input, then in checksum
:> example your program computes a constant function, in which case it is
:> easy to write another program that computes the same function.

: But it is part of the input.

: If
:> the program is part of the input, then it is also easy to write another
:> program that computes the same function. So what mathematical function
:> are you trying to compute?

: A program that computes its own checksum in order to demonstrate
: that making seemingly local changes to the program's code causes
: a change in its results.

The output has to be defined in terms of the input. A mathematical
function does not have a program, so the definition of the mathematical
function you are trying to compute cannot refer to a program.

:>
:> The whole reflective code idea really does not affect the Halting
:> problem at all.

: I agree completely. That's not the point of this particular
: argument. This argument is about whether a TM extended to have
: access to its own state transition table can be trivially
: "transmogrified" without changing its own results.

Sure there is. The TM's state transition table is constant,
so any conditional that uses the transition table can be replaced
with a hard coded true or false. The new TM will compute the
exact same result as the old TM.

Stephen

Relevant Pages
Loading