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

From: Will Twentyman (wtwentyman_at_read.my.sig)
Date: 08/18/04 

Date: Tue, 17 Aug 2004 21:43:18 -0400

Peter Olcott wrote:

> "Will Twentyman" <wtwentyman@read.my.sig> wrote in message news:4120b714$1_4@newsfeed.slurp.net...
>
>>Peter Olcott wrote:
>
>
>>"The last step is the method by which the Halt analyzer can determine
>>its invocation context. This can be a very simple feature that is
>>implemented in the Universal Turing Machine. The Halt analyzer would
>>merely ask the UTM whether or not its specifically indicated final state
>>has any state transition defined. This information is very easy for the
>>UTM to provide, it merely looks up the action associated with the state
>>in its state transition matrix table. If there is no state transition
>>defined out of the Halt analyzer's final states, then the Halt analyzer
>>can know with certainty that it was not invoked as a part of another
>>Turing Machine's execution. It can use this information to determine
>>whether or not it can safely return a result, or that it must refrain
>>from returning a result."
>>
>>My first comment is: the functionality you want to add means we are no
>>longer looking at Turing Machines, but some other type of machines. The
>
> The all depends on whether you take the Church-Turing thesis as
> a mere figure-of-speech or not. I don't.

There are other (theoretical) machines that are computationally more
powerful than a Turing Machine. Now, they are, as far as I know,
strictly theoretical even to the degree of approximating them.
Similarly, there are some machines that are strictly less powerful than
a Turing Machine. These do not non-bounded looping. However, what you
are discussing at this point is something that is not even precisely
defined.

>>burden of proof falls to you to show whether or not these modified
>>machines have the same power as a traditional Turing Machine. They may
>>have more, less, or the same. Secondly, you state that "This
>>information is very easy for the UTM to provide," but don't specify how,
>
> If you understand TM's well enough you already know how.
> If you don't understand them this well, then you could do some
> more research.

On a standard TM, the UTM has to provide it as an additional explicit
input. This raises the issue of the UTM computing that additional
input, which may be non-trivial.

>>or what happens if it lies.
>
> If you can make each and every instance throughout the entire
> universe lie each and everytime, then you have refuted me. If
> you can not, then the one or more cases where you have not
> prove that I am right.

You don't understand, each attempt of the halt analyzer must work when
run on *every* UTM, not just most. If it *ever* fails, it is not a halt
analyzer. Relying on the environment being guaranteed to be honest is a
recipe for failure.

>>Until a few more details are provided, it
>>is quite difficult to determine what is actually going on. What you
>>have right now is a sketch of what you want a proof to look like. Until
>>you fill in some more details, such as precise definitions, it is not a
>>proof.
>
> If you know the idea of TM's well-enough then all the other details
> are obvious. A state transition matrix is a very simple idea. It only
> a two-dimensional array of integers. One subscript is for the current
> state and the other one is for the current input. In the table itself
> is ActionCodes. These are just subscripts into an array of functions.

Here's the problem: you have changed your method often enough that what
should be obvious may shift with how you are thinking about the problem
at the moment. That's not how math works. You have to nail down what's
being discussed in advance. Then, if you change it later, it is much
easier to see whether the work so far breaks or not. Since it is your
idea, you are the one best in a position to describe its behavior. Now,
do you want all TM's to mystically know their state transition matrix or
do they have to compute it by some means or is it to be handed to them
from somewhere? 

-- 
Will Twentyman
email: wtwentyman at copper dot net

Relevant Pages

  • Re: The proof that I was referring to is on the website
    ... "The last step is the method by which the Halt analyzer can determine ... UTM to provide, it merely looks up the action associated with the state ... in its state transition matrix table. ... machines have the same power as a traditional Turing Machine. ...
    (comp.theory)
  • Re: The proof that I was referring to is on the website
    ... "The last step is the method by which the Halt analyzer can determine ... UTM to provide, it merely looks up the action associated with the state ... in its state transition matrix table. ... machines have the same power as a traditional Turing Machine. ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... >>another Turing Machine, or invoked independently of any other Turing ... This information is very easy for the UTM to provide, ... >>looks up the action associated with the state in its state transition ... >>What if Halt is not running on a UTM? ...
    (comp.theory)
  • Re: The proof that I was referring to is on the website
    ... >>another Turing Machine, or invoked independently of any other Turing ... This information is very easy for the UTM to provide, ... >>looks up the action associated with the state in its state transition ... >>What if Halt is not running on a UTM? ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... "The last step is the method by which the Halt function can determine ... another Turing Machine, or invoked independently of any other Turing ... This information is very easy for the UTM to provide, ... looks up the action associated with the state in its state transition ...
    (comp.theory)
Quantcast