[FOM] Simplest universal Turing machine

[Wojtek Moczydlowski]

On Thu, 25 Oct 2007, Andrej Bauer wrote:

>  "The smallest computation of intermediate degree is larger than
>   the smallest computation of maximal degree."
>
> For example: the smallest Turing machine enumerating a c.e. set of
> maximal degree is smaller than the smallest Turing machine enumerating a
> c.e. set of intermediate degree.
>
> What are some other possible examples on which we could test the
> hypothesis? And how could we express this idea more precisely?
>
> Andrej Bauer

It seems to me that one-rule string-rewriting systems are a good 
candidate to test the hypothesis. These are specified by a pair of words 
(s, t) over some alphabet, written usually as s->t. Such pair of words
induces in a natural way a (rewriting) relation -> on all words:
->(x,y) holds iff there are words q, w such that x = qsw and y = qtw.
->(x, y) is usually written x->y and read as: "x reduces to y".

The decidability of any reasonable question about infinite behaviour of 
these systems even over 2-letter alphabet has been unknown for quite some 
time. For example, given s->t, is there a word z allowing infinite
sequence of reductions : z->z_1->z_2->...?

More information about the problem can be found for example in Alfons 
Geser's habilitation thesis:

http://ginevras.pil.fbeit.htwk-leipzig.de/pil-website/public_html/geser/habil.html

Now, if the hypothesis is right, at least in the form stated on Wolfram's 
blog: "one of the predictions of PCE is that as soon as one sees something 
like a Turing machine whose behavior is complex, the system will end up 
being universal--even if its underlying rules are really simple.",
there should be a universal Turing machine among these systems, since the 
underlying rules are really simple, but their behaviors can be quite 
complex. However, if I recall correctly, when I talked about it with 
researchers, it seemed that there wasn't a clear intuition that
these systems exhibit enough complexity for this to be the case.

Wojtek Moczydlowski