[FOM] Simple Turing machines, Universality, Encodings, etc.

[Alexander Smith]

"The way in which this is achieved is to create an initial condition
 that represents an emulation of the cyclic tag system for one cycle
 (in a way that can be shown to always terminate, and therefore
 definitely not be universal), which can be transformed using a simple
 and obviously non-universal rule into an initial condition that
 represents an emulation for two cycles, four cycles, and in general
 2^n cycles."

The first 21 pages of my proof are spent in describing a construction in the 2,3 Turing machine that represents an emulation of the cyclic tag system for any number of steps. I was simply referencing that construction. Again, the preprocessor does /not/ run the cyclic tag system itself, but rather translates it into a form that can be read by the 2,3 Turing machine, which then emulates it; the first 21 pages of my proof are taken up with stating what form this needs to be, and proving that when given that input the 2,3 Turing machine does emulate a cyclic tag system: note that each separate part of the cyclic tag system maps to a separate part of the input tape to the 2,3 Turing machine, so it is definitely the machine that is running it.

The rest of my proof goes on to describe a simple non-universal rule that can take the initial condition that corresponds to the one-cycle emulation and transform it into an initial condition that corresponds to a two-cycle emulation, then to a four-cycle emulation, and so on; concatenating all these initial conditions forms the intial condition to the 2,3 Turing machine itself. The transformation again keeps separate parts of the input cyclic tag system separate; at no point is it running or emulating the cyclic tag system.

I apologise if that paragraph was slightly unclear; in the context of the rest of the proof, it's clearly a reference to everything that precedes and everything that follows, but it seems that that isn't clear to someone who hasn't read the rest of the proof.

As for stating that the initial condition is created in a non-universal way: I'm not sure that I have an exact definition of this statement, but it appears to hold true for all reasonable definitions I can think of. It's produced by an infinite series of mechanical transformations on the one-cycle initial condition (which are described in the proof) with no interaction between different parts of that initial condition; it's therefore non-universal for much the same reason as a context-free grammar is non-universal (although an infinite amount data is written onto the tape, only a finite amount of data affects what happens at each transformation, and the rest is merely negated, translated, added to a constant, etc., but never actually read during the transformation).

> I would find it very helpful if you would compactly describe the IO
> interface of your machine, involving the algorithm for creating the
> input tape.

The algorithm for creating the input tape is explained on pages 4-5, 8-9, 10-12, 16, 19, and 23-26; page 20 explains how to calculate minimum values for some numbers which are merely defined as 'sufficiently high' in the original algorithm. I agree that the constructions are mixed in with the proofs of their correctness, but they are far from trivial and in fact make up much of the proof. To see the construction of the one-cycle initial condition (the initial condition that represents an emulation of the cyclic tag system for 1 cycle), look for the sections headed 'Initial condition' in the proof itself, which will explain the construction down to system 3, and then it's a case of using the equivalence of system 3 and system 0 (the 2,3 Turing machine) to translate the construction into an initial condition for the system 0 tape. The construction is very large; programs that demonstrate the algorithms needed in an earlier version of the construction are appended to the proof (the main differences are a change to the start of the initial condition and the addition of some extra large integers in system 5); however, I never managed to run the construction from start to finish on my computer because it was simply too large. (I did manage to run it from a cyclic tag system down to system 4, and from system 5 down to a 2,3 Turing machine program, though, so every step in the construction was tested.) I'm not sure if I can explain such a long algorithm compactly, except by referring you to the proof or to the computer code that accompanies it. A non-rigorous description of the IO interface is to say: a cyclic tag system is converted to a finite section of tape that represents it by an algorithm that's guaranteed to terminate (the finite amount of output and the guaranteed termination show that this step is not itself doing the potentially infinite calculation that the cyclic tag system describes); that section of tape is then repeatedly transformed with the transformed version appended to it, where the transformation step itself is not doing any simulation of the cyclic tag system (it takes all the sections of the tape that represent the original cyclic tag system separately, and transforms them each with a set of mechanical rules that don't care about more than a fixed finite amount of what data is already there and which therefore cannot be emulating the cyclic tag system, just as a finite-state machine cannot emulate a cyclic tag system). That's what determines the input to the 2,3 Turing machine. There are various ways to extract the behaviour of the cyclic tag system from the output of the 2,3 Turing machine; rather than try to describe the (simple) algorithm for doing so, I refer you to System0To3CompressC in the code appended to the proof, which translates the history of execution of the 2,3 Turing machine into a list of values removed from the start of the working string of the cyclic tag system it's emulating.

--
Alex Smith


  _____

From: fom-bounces at cs.nyu.edu on behalf of Rob van Glabbeek
Sent: Fri 02/11/2007 02:48
To: AIS523 at bham.ac.uk
Cc: fom at cs.nyu.edu
Subject: Re: [FOM] Simple Turing machines, Universality, Encodings, etc.



> You appear to have misunderstood my proof.

I have actually not read all of your proof, as I assume its validity
has been checked by others. The point of the ongoing debate is, as I
understand it, whether the complex encodings in your IO interface are
so liberal that they imply a definition of universality that would
imply universality of accepted non-universal systems.

I therefore scrolled straight to your section entitled
      "An initial condition obtainable in a non-universal way".
There I read:
"The way in which this is achieved is to create an initial condition
 that represents an emulation of the cyclic tag system for one cycle
 (in a way that can be shown to always terminate, and therefore
 definitely not be universal), which can be transformed using a simple
 and obviously non-universal rule into an initial condition that
 represents an emulation for two cycles, four cycles, and in general
 2^n cycles."

To me this sounds like saying that in order to obtain the initial
condition you have to run (or emulate) the cyclic tag system for more
and more cycles. But now you write:

> The algorithm that writes the input tape in my proof doesn't involve
> calling a cyclic tag system or any other sort of universal system;

To check what is really going on, one would have to read the entire
paper, as it appears the various constructions are all mixed in with
the proofs of their correctness, and spread over many pages.
I would find it very helpful if you would compactly describe the IO
interface of your machine, involving the algorithm for creating the
input tape.

And what ought to be implied by that is a definition of what
constitutes a universal Turing Machine. Getting this definition
explicit would make it better possible to test it.
So far you state that the input tape ought to be created "in a
non-universal way", but how to define "non-universal" in this sense is
still somewhat vague (to me at least) ...

Rob
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom