- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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

Date: Sun, 01 Jul 2001 07:47:55 -0400

Jacques:

Why not?

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!! =)

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.

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

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