[FOM] Complexity of (Universal) Turing Machines

[Vaughan Pratt]

Steve Gardner wrote:
> So here's my question: is state-symbol product the accepted standard 
> by which the complexity of any TM, regardless of formalism, is measured? 
> If it is, and if Smith's claim to have proved the universality of 
> Wolfram's (2,3) TM stands up, then can this TM be regarded as the 
> simplest possible UTM, without the need for any disclaimers about 
> formalism?

No, for various reasons, which taken together point up the need for such 
alternatives as Kolmogorov complexity as already pointed out, or in your 
case Wallace's MML as a viable and practical alternative to Kolmogorov 
complexity that avoids some of the shortcomings of the latter addressed 
e.g. in the paper http://arxiv.org/abs/0804.3459 that Zenil mentioned on 
Tuesday (which however addresses only limiting cases of pathological 
variations and not specific variations arising naturally between extant 
languages).

First of all, state-symbol product is by no means a stable measure under 
variation of formalism.  The example I gave on this list in late 
November of a read-only TM with a blank two-dimensional semi-infinite 
tape (i.e. the upper right quadrant of the plane), started at an 
arbitrary point on the tape, illustrates this nicely.  Suppose the 
formalism counts only those symbols the TM is allowed to write, while 
however allowing the TM to detect end-of-tape (in this case the two 
edges of the quadrant).  Then for a read-only TM the number of writable 
symbols is zero, whence the state-symbol product is always zero 
regardless of how many states the machine has.  Yet such a machine is 
equipollent (even up to bisimulation) with a two-counter machine, and 
hence can be universal.

Restricting to the TM formalisms that were *considered* for the Wolfram 
prize (one cannot say "allowed" because the prize guidelines far from 
discouraging creativity in choice of formalism actually encouraged it 
within reasonable but otherwise vague limits), there is still some 
sensitivity to choice of formalism that tends to undermine state-symbol 
product as a complexity measure for Turing machines.

Universality of Turing machines is customarily defined with respect to a 
given presentation of Turing machines, e.g. as 4-tuples suitably 
encoded.  Moreover the presentation is presumed finite in the sense that 
all but finitely many symbols of the infinite tape containing the given 
presentation are blank.

The formulation of "universal Turing machine" by Wolfram's camp departs 
from this in two regards.  First the presentation aspect is 
existentially quantified: a Turing machine T is universal in Wolfram's 
sense when there exists a presentation (encoding convention) for which T 
is universal (in the usual sense) for that presentation.  (So part of 
the Wolfram prize was to find an encoding for which the subject machine 
was universal.)  Second, tapes with infinite nonblank background are 
permitted, e.g. tapes with a fixed infinite periodic background over 
which the finite input is superimposed.

Both departures reinterpret state-symbol complexity, potentially 
nontrivially, though I'm not aware of any careful assessment of that 
impact.  In any event even if state-symbol product were to be taken 
seriously as a measure one would not do so without first settling which 
if any of these departures were allowed.  (It's hard to imagine any 
scenario in which the second was considered acceptable, and the first 
seems quite problematic though potentially of interest nonetheless.)

Smith was able to prove the subject machine universal only by a third 
departure: the relaxation of periodicity of the background to a 
background that while nonperiodic was sufficiently regular to be written 
by a one-counter machine.  Since one-counter machines are not themselves 
universal, Smith argued that his relaxation of Wolfram's criterion could 
not turn a nonuniversal machine into a universal one.  This was the step 
in Smith's argument that was initially objected to by some at WRI, but 
subsequently accepted after Smith modified his handling of the 
nonperiodic background.  (One is reminded of Alfred Kleiner's treatment 
of Einstein's thesis, which he returned to Einstein with the complaint 
that it was too short, but then accepted without further comment after 
Einstein added a sentence.)  My own objection was that furnishing a 
Turing machine T with a counter could turn a non-universal machine into 
a universal one, e.g. if T were itself a one-counter machine.

Hopefully you only need this sort of background by way of comparing MML 
with Kolmogorov-like measures and not as an actual proposal to use the 
latter in biology.  I was dubious even of MML for that application when 
Chris Wallace described it to me in the Physics School corridor in 1967, 
but I would be even more dubious of Kolmogorov complexity.  Occam's 
Razor unnecessarily handicaps the explanatory power of theories and is 
thus felled by its own hand.

Vaughan Pratt