[FOM] Complexity of (Universal) Turing Machines
Steve Gardner
Steven.Gardner at arts.monash.edu.au
Mon Apr 21 20:30:07 EDT 2008
I hope you'll forgive a post from a non-mathematician. For a paper
defending the merits of Bayesian inference using Wallace's Principle of
Minimum Message Length, my colleagues and I need to talk about the
simplest possible Universing Turing Machine, and I have a question about
how to characterise that notion.
But first, some extremely brief background (all taken from Wallace
(2005, Chapter 2): for the purposes of Bayesian inference, choice of a
UTM can be regarded as equivalent to choice of a prior probability
function. For any UTM T and finite string D (regarded here as the data),
there is guaranteed to be a shortest program of length L which outputs D
when input to T. So the UTM T can be regarded as assigning a prior
probability of 2^-L to seeing D. The interest in the choice of the
simplest possible UTM is that it can reasonably be regarded as
equivalent to a choice of prior probability function reflecting complete
prior ignorance about the data. This answers a familiar objection to
Bayesianism, that there is no objective or non-arbitrary way to
characterise prior ignorance.
I am aware that different formalisms exist for describing Turing
machines: e.g., Turing's state tables, the tag systems of Post, the
cellular automata of Wolfram. I originally thought that to each of these
there would correspond a different way of characterising the complexity
of a TM. In particular, I originally thought that state-symbol product
was used to characterise the complexity of TMs described a la Turing,
but that different (and non-commensurable) characterisations would be
needed to describe the complexity of tag systems and cellular automata.
If that were right, claims about "the simplest possible UTM" would have
to be qualified with the disclaimer "relative to some formalism for
describing TMs".
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?
Thanks,
Steve Gardner
--
Steve Gardner
School of Philosophy and Bioethics
Faculty of Arts, Monash University
Steven.Gardner at arts.monash.edu.au
Office: W903A/11 ph: (613) 9902 0017
-- Anything that can't go wrong, will go wrong.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Steven_Gardner.vcf
Type: text/x-vcard
Size: 242 bytes
Desc: not available
Url : /pipermail/fom/attachments/20080421/5c9bc434/Steven_Gardner.vcf
More information about the FOM
mailing list