Wei Dai writes:
> On Tue, Jan 20, 1998 at 02:46:54PM -0800, Hal Finney wrote:
> > I think there would be a mapping between mathematical structures and TM
> > programs.
> But there are some mathematical strctures that can't be described as a
> formal system. For example the set of all true statements about integers,
> or a universe that contains an oracle for the halting problem. One can
> even argue that most mathematical structures can not be described as
> formal systems, since the set of all mathematical structures is not
> countable. (Isn't every real number a mathematical structure? How about
> every function on the real numbers?)
I think the meaning of "mathematical structures" is somewhat vague here.
I was suggesting an equivalence between mathematical structures as Tegmark
uses the term and TM programs. He does not refer to a specific real number
as a mathematical structure. Rather, the set of all reals along with the
rules for arithmetic on them forms a type of field, which is the kind of
structure he is talking about. You can create a formal system which defines
this field, and you could write a TM program which would enumerate all
valid proofs within this system, in order of size.
A single real number in isolation is not a mathematical structure in this
sense because there are no operations you can perform on it.
Getting back to my original point, maybe a better way to relate Tegmark's
idea to the TM concept is to consider a subset of TM programs, those which
enumerate valid proofs of the formal systems which describe the various
mathematical structures. These would then be the possible universes in
> > Using Schmidhuber's mapping, the universe states would be 0, 1, 10, 11,
> > 100, 101, 110, 111, .... I don't see any simple mapping which would make
> > this look at all like the universe we live in. For example, one of the
> > characteristics of this kind of counting is that there is a lot of change
> > at the right hand side and very little at the left, and we don't really
> > see that kind of behavior in our universe, which is somewhat homogeneous.
> This argument doesn't work because we can't directly observe the state of
> the universe and its evolution, so we can't say that it is not changing
> only at the right hand side. If we accept Schmidhuber's interpretation,
> there is no way to rule out the possibility that we're living in the
> counting universe because everything eventually appears in it during its
> evolution, including us. If we were living in the counting universe, of
> course all of our memories and perceptions would have no basis in reality.
I'm not sure I follow you here. Are you suggesting that our observations
of the universe's history might be in error, that we might be instantiated
for a single instant with all of our memories of the past being illusions?
We could write down the state of the universe at this instant as a long
string using a simple mapping, and at some point the counting TM will
emit this string. At that instant we will all exist with our memories
of the past, but none of that past will actually have happened. Is this
> So my problem with Schmidhuber's interpretation is even ignoring the
> mapping problem, I don't see how it would assign a low probability to us
> being in the counting universe. Perhaps he would comment if I'm
> misunderstanding him.
The problem then is not so much with the objective question of whether we
live in the counting universe, which an outside observer could easily
answer, but rather with the difficulty of us as residents in the universe
knowing the answer.
A more extreme case occurs if the counting program works in trinary,
using the 0/1/comma alphabet. Now it outputs not only all numbers, it
outputs all possible comma-separated sequences of numbers. It eventually
outputs not only every possible state, but every possible sequence of
states, including the entire history of our universe. This history would
be a subset of an enormously larger output string, all created with a very
short (and therefore a priori probable) input program.
All I can suggest about these problems is that they would imply that the
universe will shortly cease to behave lawfully. When we don't observe
this, we can reject this possibility. Otherwise we are forced to say
that all our perceptions are illusions, that our memories are false,
that we ourselves may be simply memories of some future self. Logically
we can't rule this out, but it does not seem reasonable. If we lived in
the counting universe, there is no reason why the universe should seem
lawful in the sense we see.
> I think the solution to the mapping problem is to assume no mapping. A
> Turing machine is a universe, and its output given some region as input IS
> the content of that region, not merely the encoding of the content of that
> region. Otherwise, as you point out, you could hide arbitrary amount of
> complexity in the encoding function.
> The interpretation I gave earlier already implicitly assumes no mapping,
> so I don't think it suffers from the mapping problem.
You solution is somewhat different in nature from Schmidhuber's.
Your set of possible universes is more structured than his. You have
a coordinate system, you have regions (which may imply a certain amount
of continuity in the coordinates). He had binary strings to represent
the universe state, which would allow for a wider set of possible
I'm not sure you can fully avoid the mapping problem with your approach.
There is still a mapping involved in the choice of coordinates.
With a sufficiently exotic coordinate system, I suspect we could map
our universe's state to the output of a trivial program.