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

stephen_at_nomail.com
Date: 08/17/04 

Date: 16 Aug 2004 22:58:23 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:
:> : 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.

But if it is not portable, you are arguing that a particular
architecture can solve problems that others cannot. If you
are not trying to make that argument, you should only consider
code that is not dependent on a particular architecture.

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

But it can also 'not be simulated'. The simulation is not going
to be more powerful than the machine doing the simulation.
Any problem that can be solved on a computational model that allows
you to mess with return values can also be solved on a computational
model that does not allow you to do so.

And I do not think it is meaningful to talk about simulation here.
If a language has no return statements, it is meaningless to talk
about whether or not a return statement changes the result of a calculation.
A program in such a language that solves the same problem need not
explicitly 'simulate' a return statement.

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

But the simulation is not going to be more powerful. Do you
agree that any problem that can be solved can be solved without
simulating the ability of a return statement changing the calculation?

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

It does not matter what your TM is doing, it cannot access its state
table. You are confusing the simulator and the simulation.
There is no problem that can be solved by a simulated TM that
cannot be solved by a non-simulated TM.

Stephen

Relevant Pages

  • Re: Havent done anything real with OOP yet.
    ... >> Whether it takes a microsecond or a year to complete the calculation of ... That's exactly what the simulation would be used for. ... >for the heat flow calculations for whatever reasons. ... Sampling time for the controller. ...
    (comp.object)
  • Large scale engineering calucations performance bottlenecks
    ... optimizing variables. ... DRAM -- I should have enough physical memory, but Excel ... but the calculation time even without ... this simulation is best ...
    (microsoft.public.excel.misc)
  • Re: Avoiding a range in recalculation
    ... Excel and turning off calculation would not be acceptable. ... Sub Simulation() ... The sheet includes a result summary area which summarises data ...
    (microsoft.public.excel.programming)
  • Re: What is the Result from Invoking this Halt Function?
    ... :> calculation that could be accomplished in normal C/C++ could be accomplished ... I know I can write this on one machine for one programming language. ... to be more powerful than the machine doing the simulation. ... :>: the TM can query the UTM about its state transition table. ...
    (sci.logic)
  • Re: TRM - Morbidity has set in, or not?
    ... I think now is a good time to revisit Keith's statement about simulation. ... Each node has a specific voltage. ... an AND gate type and an OR gate type might drive their output pins to different values with the same propagation delay while two different AND gate types might drive the output pins to the same value with a different propagation delay. ... Each device subtype requires only a name and a state transition function. ...
    (comp.databases.theory)