[FOM] Complexity of (Universal) Turing Machines
Timothy Y. Chow
tchow at alum.mit.edu
Wed Apr 23 17:33:36 EDT 2008
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
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.
More information about the FOM