[FOM] Simplest universal Turing machine
wojtek at cs.cornell.edu
Mon Oct 29 21:43:39 EDT 2007
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:
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.
More information about the FOM