Re: lowly complexity

From: Marchal <marchal.domain.name.hidden>
Date: Mon Jul 2 03:00:41 2001

Joel (in his reply to Jacques Mallah):

>At this time, none of the elementary one-dimensional minimal
>cellular automata appear capable of universal computation.
>[...]
>Maybe three dimensions is the minimum needed to do this
>successfully. ?


There exists one dimensional *universal* automata.
If minimality + universality implies the necessity of 3
dimension, that would be a result vindicating your
choice of minimal universal CA .... 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).

>Note: Some of you will point to the Game of Life as an example of a
>two-dimensional universal computer - using gliders as information
>channels.
>
>But it is not clear to me that such an automaton could actually be
>made to compute the workings of a minimal celllar automaton (one
>that generates all configurations). Yes, I have seen the examples
>of the Game of Life working as a Turing Machine. But let me just
>say I'm not convinced it will work for infinite computational
>processes like the minimal CA. 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 ".

>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.
About the slow-down. If you want no slow-down you should buy
QMUCA! (Quantum MUCA). 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.

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).

Bruno
Received on Mon Jul 02 2001 - 03:00:41 PDT