Re: lowly complexity

From: Joel Dobrzelewski <dobrzele.domain.name.hidden>
Date: Sun, 01 Jul 2001 07:47:55 -0400

Jacques:

> You guys are going about it all wrong. Sure, some computers seem
> simpler than others. But there's no one way to pick the simplest.

Why not?

> The set of all is the simplest possibility, rather than choosing
> one "simple" program. (Joel's 3 dimensional cellular automata
> are particularly ridiculous to me. How could he think the 3-d is
> not anthropically chosen?)

I struggle very much with the reasons why the automaton should be
three-dimensional. And at this time, I have no adequate answer for
you. Perhaps it is not.

But... let me say this:

We do not claim that this magic automaton needs to be three-
dimensional. We only claim that it is minimal (generates all
finite configurations) and computationally universal (can perform
any computation).

It is the latter part (computational universality) that may require
three dimensions. But honestly this is just a hunch.

At this time, none of the elementary one-dimensional minimal
cellular automata appear capable of universal computation.

Certainly it would seem that there might be a two-dimensional
automaton that is both minimal (generates all configurations) and
also computationally universal.

But what if there isn't? Most computer scientists seem to agree
that computational universality requires crossing signals paths -
to get information from one place to another without disrupting the
flow of other information streams.

Maybe three dimensions is the minimum needed to do this
successfully. ?

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.

What we need is something that is minimal (generates all
configurations) AND computationally universal (capable of
performing any computation)... thus generating ALL programs.

Maybe three dimensions is the only way to do this. ? I don't
know.

But I do know this...

We'll never know if we don't look!! =)

> All possible algorithms should exist: TMs, CAs, etc.

As we know, from a computational point of view, Turing Machines are
equivalent to cellular automata.

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.

> The typical machine on the bottom should therefore be of huge
> dimension, with a huge number of states, etc.

That's going to be a very difficult thing to study.

But let me look at your paper, as this is new to me.

Joel
Received on Sun Jul 01 2001 - 04:48:43 PDT