[FOM] Complexity of (Universal) Turing Machines

[Timothy Y. Chow]

Steve Gardner <Steven.Gardner at arts.monash.edu.au> wrote:
> However, reading the discussion of Alex Smith's recent claim to have 
> proved the universality of one of Wolfram's cellular automata, I see 
> that state-symbol product is also used to characterise the complexity of 
> Wolfram's cellular automaton: it is referred to as a 2-state, 3-symbol 
> TM. 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?

This subject has certainly not yet matured to the stage where one can 
dispense with disclaimers about formalism.  Note that even if there were 
an "accepted standard" for measuring the complexity of a TM, that would 
not necessarily be enough; I think you want more than a universally 
accepted *convention*---you want a *canonical* measure.

Kolmogorov complexity theory says that the choice of formalism makes no 
difference up to a constant, but the constant can be arbitrary, and there 
is no obvious way to make a canonical choice.

Coincidentally, the paper "Towards a stable definition of 
Kolmogorov-Chaitin complexity" by Delahaye and Zenil just appeared on the 
ArXiv (http://arxiv.org/abs/0804.3459).  I have not digested it, but it 
may be relevant to your question.

Tim