[FOM] Simplest universal Turing machine

[Andrej Bauer]

Timothy Y. Chow wrote:
> I was wondering if FOM readers have any comment about Stephen Wolfram's 
> announcement today:
> 
> http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html

Wolfram's Principle of Computational Equivalence (PCE) states that "when
one sees behavior that isn't obviously simple, it'll essentially always
correspond to a computation that's in a sense maximally sophisticated".

Clearly, it is possible to falsify PCE by cherry-picking examples one
looks at. But what I think Wolfram has in mind is: if you start looking
at smallest or simplest things first, then you will first see
trivialities, then you will encounter maximal sophistication, and only
later will you get to "intermediate" sophistication.

Perhaps there is a way to understand this as follows: take a notion of
computation (Turing machines, C++ programs, cellular automata, deductive
systems) with a suitably chosen notion of reduction (such as "can
simulate" or "has lower Turing degree than") and a reasonable measure of
complexity (number of states, size of program). Then PCE could be
understood as

  "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