RE: Is the universe computable?

From: David Barrett-Lennard <dbl.domain.name.hidden>
Date: Tue, 4 Nov 2003 15:52:36 +0800

An interesting idea.

Where can I read a more comprehensive justification of this
distribution?

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.

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.

- David


-----Original Message-----
From: Hal Finney [mailto:hal.domain.name.hidden]
Sent: Tuesday, 4 November 2003 2:24 PM
To: everything-list.domain.name.hidden
Subject: RE: Is the universe computable?

IMO the best idea we have discussed for why the universe is and remains
lawful is that the set of descriptions (equivalently, programs) for
the universes are governed by the Universal Distribution. This is the
description where a string whose shortest description has length n bits
is given measure 1 / 2^n.

An heuristic argument for this distribution is that if programs are
self delimiting, then there are 2^x more programs of length n+x than
of length n, created by appending the 2^x x-bit strings to each n-bit
program. Since the appended x bits are never executed, all 2^(n+x)
of these programs are the same as the basic 2^n programs.

A program which says "obey these simple laws" is shorter than a program
which says "obey these simple laws for a zillion steps, then start
obeying these other laws", or a program that says "obey these simple
laws
everywhere except where this incredibly complicated configuration
occurs,
and then do this complicated other thing."

Hal Finney
Received on Tue Nov 04 2003 - 02:53:51 PST