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

[Alexander Smith]

You appear to have misunderstood my proof. 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; about the most complicated thing it invokes is the rule 60 cellular automaton, which is known to be computationally reducible (any element at any step in its evolution can be deduced from the parity of a binomial coefficient, for instance). It doesn't run a cyclic tag system; it simply converts the rules of a cyclic tag system into a (somewhat complex) representation that can be read by the 2,3 Turing machine. For instance, regions of the 2,3 Turing machine's tape that represent the initial input given to the cyclic tag system are distinct on the tape from regions that represent the first string to be added in the cyclic tag system, likewise for the second string and so on. (There are an infinite number of such regions, each physically longer than the last and produced from the last by a mechanical and non-universal process.) The regions that represent the initial input are also affected by the cyclic tag system as a whole, but this influence is limited to a representation only of the 'size' of the system (where 'size' is rigorously defined), not on its details. So I am not using a cyclic tag system to create the initial tape, nor am I running it a finite and pre-determined number of steps at a time (the 2,3 Turing machine itself is the only system involved that runs the cyclic tag system). The difference is that between interpreting a computer program (your example), and doing text processing on the text of a computer program (my proof); the first runs the program, and is therefore universal, whilst the second merely processes it in a mechanical way (which can be universal or non-universal, and is non-universal in my proof).
 
-- 
Alex Smith

________________________________

From: Rob van Glabbeek <rvg at cs.stanford.edu>
To: fom at cs.nyu.edu
Date: Tue, 30 Oct 2007 20:45:48 +1100
Subject: Re: [FOM] Simple Turing machines, Universality, Encodings, etc.
Reply-To: Foundations of Mathematics <fom at cs.nyu.edu>

(snip)

 Producing the input tape involves calling an universal TM.  Smith
 uses a cyclic tag system, that is also universal, in the very same
 way. He states that the tape is written "by an obviously
 non-universal algorithm". This because to write a section of tape,
 the universal system is run a finite and pre-determined amount of
 steps at a time.

(snip)