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

Rob van Glabbeek rvg at cs.stanford.edu
Thu Nov 1 22:48:50 EDT 2007

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


More information about the FOM mailing list