[FOM] Complexity of (Universal) Turing Machines

[Steve Gardner]

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