# RE: Is the universe computable?

```[Note that I take the liberty of replying only to the list, so that
copies of my messages.]```
```
David Barrett-Lennard writes:

> An interesting idea.
>
> Where can I read a more comprehensive justification of this
> distribution?

Juergen Schmidhuber, who originated many of these concepts, has a
number of articles on distributions.  He is not a big fan of the UD
but I think it is appropriate for what seems to me the simplest model
of computing, Turing equivalent machines.  He has a page on the UD
at http://www.idsia.ch/~juergen/icmlkolmogorov/node2.html and if you
look around his site you can find much more.

Chaitin's work on Algorithmic Information Theory is related as well,
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/.  He works with a measure
of complexity based on program bit length that implicitly points to
the UD.  Chaitin's most famous result relates to the constant Omega,
the probability that a random program will halt, where again the programs
are implicitly selected according to the UD.

> If a number of programs are isomorphic the inhabitants naturally won't
> know the difference.  As to whether we call this one program or lots of
> programs seems to be a question of taste and IMO shows that "probability
> calculations" are only relative to how one wants to define equivalence
> classes of programs.

The idea is that if all program strings are equally probable (admittedly
a problematic assumption given that programs can be infinitely long),
that implicitly leads to the universal distribution as a measure.
This solves the problem you raised (about why the universe is lawful)
in a very natural way.

> I would expect that the probability distribution will depend on the way
> in which we choose to express, and enumerate our programs.  Eg with one
> instruction set, infinite loops or early exits may occur often - so that
> there is a tendency for simplistic programs.  On the other hand,  an
> alternative instruction set and enumeration strategy may lead to a
> distribution favoring much longer and more complex programs. Perhaps it
> tends to complicate programs with long sequences of conditional
> assignment instructions to manipulate the program state, without risking
> early exit. Importantly such "tampering" doesn't yield a program that is
> isomorphic to a simple one.  We seem to have a vast number of
> complicated programs that aren't reducible to simpler versions.  This
> seems to be at odds with the premise (of bits that are never executed)
> behind the Universal Distribution.

If I understand your concern, this has been shown to be not a problem.
Any universal computer can simulate any other using a prefix of fixed
size.  Therefore the size of minimal programs for any two universal
computers can vary by only a constant, and the UD's determined by these
two computers will similarly agree to within a constant factor.

Hal Finney

P.S. In http://www.escribe.com/science/theory/m3666.html I discussed a
way in which the UD might actually give us reason to expect the universe
to be surprisingly unlawful.

```