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
