Re: lowly complexity

From: Joel Dobrzelewski <>
Date: Mon, 2 Jul 2001 08:55:19 -0400


> There exists one dimensional *universal* automata.

Yes, but it has many internal states and is not minimal. Also... it does
not specify something very important...

What is this one-dimensional universal automaton doing?

What program is it running?

> If minimality + universality implies the necessity of 3 dimension,
> that would be a result vindicating your choice of minimal universal
> CA ....

Yes, that is the hope.

> except that, remember UDA, to compute my futur I must necessarily
> take into account *all* emulations of me done by all possible
> universal machines because they are all emulated by the UD, or by the
> MUCA (Minimal Universal Cellular automata).

But my goal is not to compute my future. We cannot do that any faster than
the Universe itself does it. My goal is only to understand the underlying
mechanism... The Program.

>> And as I said before, The Game of Life itself is almost certainly
>> not minimal, (definitely not reversible) so this would seem to rule
>> it out as "The Automaton" that runs everything.

> I disagree, for a change. You can write a universal dovetailer as a
> pattern of the game of life. It will generate your MUCA. Of course if
> you are patient enough you can write directly an emulator of your
> MUCA directly as a Game of Life pattern. I agree the Game of Life,
> like FORTRAN, is not minimal, but You can simulate the MUCA in
> FORTRAN and you can simulate the MUCA in "Game of Life ".

Yes, this is all true. I do understand all universal computers are
equivalent. But again: What program are these machines running? It is
becoming clear to me - that is the real question.

>> But from an abstract point of view, it may be difficult to
>> implement a Turing Machine with no ad-hoc assumptions about time and
>> space (e.g. the moving read-write head) and infinite slow-down.
> Mmmh ... Are you not contradicting yourself. I ask you what does run
> your MUCA, and you answer me that it exists abstractly. Why should
> not Turing machine deserve that type of existence? The Turing "time"
> and "space" is akin to the the MUCA time-step and space too.

Yes, you may be right. I feel I am contradicting myself a little here. And
since this is probably one of the weakest points of my argument, I don't
push it too hard. :-)

Still... it is easier for me to imagine the cellular automaton, with its
discrete time and discrete space.

I keep wondering: Exactly how does the Turing Machine read-write head move?
What propels it? What is fluid motion?

If we try to make discrete the smooth motion of the read-write head, then
the one-dimensional Turing Machine becomes a two-dimensional cellular
automaton! And then we are back to the original problem... What is it
computing? Is it minimal? Does it compute all finite configurations?

> About the slow-down. If you want no slow-down you should buy QMUCA!
> (Quantum MUCA).

Certainly. Do you have one for sale? How does it work? ;-)

> But the slow-down can be seen only by some putative absolute
> 3-observer, the 1-observer "inside" the universal simulation will not
> see a slow-down, because, as you agreed, he cannot be aware of
> delays.

Yes, this is true. Again, I try not to stress these points too much. :-)

> Like Jacques Mallah (on this point) or George Levy (apparantly on
> all points!) I agree that for fundamental matters the choice of a
> precise universal representation does not matter. As you should: I
> don't see how you will escape that point after having answer "yes" to
> the ten UDA-question. (More on this in my reply to your answer to
> question 9 and 10).

Yes, I think I agree too. The representation cannot matter.

So we agree the universe is a computer. Now what is it running? Which
program is it executing?

Received on Mon Jul 02 2001 - 05:56:16 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST