[FOM] Simplest universal Turing machine

[joeshipman@aol.com]

>-----Original Message-----
>From: Andrej Bauer <Andrej.Bauer at fmf.uni-lj.si>
>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".
...
>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.
...
>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.

PCE is much stronger than this. Wolfram surely meant "isn't obviously 
simple" to cover behaviors that were complicated but recursive. Nobody 
knows any non-contrived example of a computation of intermediate 
degree, let alone a small one.

In order to make PCE precise, one must explicate "obviously simple", 
but PCE doesn't need to be precise to be refutable. All one needs to do 
to refute it is produce a process which

i) is simpler to define than Wolfram's "universal" examples
ii) does not obviously fail to be c.e.-complete
iii) is nonetheless provably not c.e.-complete

-- JS
________________________________________________________________________
Email and AIM finally together. You've gotta check out free AOL Mail! - 
http://mail.aol.com