2
$\begingroup$

I was reading on Complex Systems journal and found a paper where the author states that a cellular automaton can be viewed as a computer.

In the introduction part:

Cellular automata can be viewed as either computers or logical universes where computers may be embbed.

  1. What i am trying to understand is, is it always a given Cellular Automaton is a computer ?

    like Elementary Cellular Automata {ECA} rule 110 and rule 90, i know that rule 110 is universal which makes it a computer but what about rule 90 ... what about other ECA rules are they also computers ?

  2. Suppose we have a cellular automaton (x), how do we know that it is a logical universe (as stated by the author), how can we know if it is a logical universe where computers can be embedd in or not and how can we know if it is just a computer ?

  3. I know that logical universes are Cellular Automata, but what dimensions these universes should be to implement a computer easily, 1D like ECA or 2D like Conway's Game of Life ?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ "can be viewed as" != "is a". Also, define "computer"? $\endgroup$
    – Raphael ♦
    Oct 19, 2015 at 13:36
  • 5
    $\begingroup$ You should focus on what the thing does, not on exactly what name is best to apply to it. Suppose somebody tells you that the fastest way to get from the airport to the city centre is by car. Your question is like trying to engage them in a long and detailed discussion about whether a taxi is a car, and what you should do if the taxi at the head of the line is a minivan because maybe a minivan isn't a car and... When somebody makes an informal statement like "... can be viewed as...", they're just trying to give you intuition. Don't obsess about the details of informal statements. $\endgroup$
    – David Richerby
    Oct 19, 2015 at 13:40
  • 1
    $\begingroup$ @ rap well, i wanted to say it is a simulation but didn't know how to say it but i think if you view something as x, then that thing can do the job of x just like ECA rule 110 which simulates universal turing machine so rule 110 is viewed as a universal turing machine and acts as a universal turing machine .. is that right ? $\endgroup$
    – abc
    Oct 19, 2015 at 13:42
  • 1
    $\begingroup$ @David seems logic, but for example i would like to know what to do if there is a minivan ahead of me, what if just the taxi is defined and not the minivan, i want to relate this exact moment to Cellular Automata, how this would be descibred ... is there a resource i can read about similar situations ? $\endgroup$
    – abc
    Oct 19, 2015 at 13:51
  • 4
    $\begingroup$ The statement you quote is informal and has no formal content. It is there for your intuition. If it doesn't help you, ignore it. $\endgroup$
    – Yuval Filmus
    Oct 19, 2015 at 14:14

1 Answer 1

Reset to default
5
$\begingroup$

"... is it always a given Cellular Automaton is a computer?"...

I interpret "is a computer" as "being capable of universal computation" or in other words "being capable of simulating an arbitrary Turing machine".

The answer is clearly NO; a trivial example is a CA that doesn't modify the input:

0[0]0 -> 0
0[0]1 -> 0
0[1]0 -> 1
0[1]1 -> 1
1[0]0 -> 0
1[0]1 -> 0
1[1]0 -> 1
1[1]1 -> 1

(rule 204)

According to Wolfram's (qualitative) classification, only type-4 CAs exhibit a behaviour that can potentially be "universal". But it is an informal statement (like many others in Wolfram's NKS) ... in order to say that a particular CA is/is not Universal you must prove it formally.

For a more rigorous introduction to the argument I suggest you to read some research articles on the subject, for example: Kristian Lindgren, Mats G. Nordhal. Universal Computation in Simple One-Dimensional Cellular Automata. Complex Systems 4 (1990) 299-318

Or - for a good, more general, introduction to computational universality - read Chapter 7: The Grand Unified Theory of Computation of the (IMO excellent) book: Cristopher Moore, Stephan Mertens. The Nature Of Computation (2011)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.