8

Here are some "nearby best" references, for what it's worth. It would seem the way to go on this question is to reduce it to a question on "noisy Turing machines", which have been studied (somewhat recently), and which are apparently the nearest relevant area of the literature. The basic/general/reasonable answer seems to be that if the TM can resist/correct ...


7

The beast is extremely powerful, for example we can build a TM $M$ that accepts every string of the form $L_Y = \{ r\; 0^n \; 1^m\;A \mid m \leq n \}$ and rejects every string of the form $L_N = \{ r\; 0^n \; 1^m\;A \mid m > n \}$ The idea is to transform the first $r$ into $R$ and then let the head reach the middle of the string then do a "stateless"...


7

Most of the patterns in my collection at http://www.ics.uci.edu/~eppstein/ca/replicators/ were found with a somewhat different heuristic search process, that was intended to find puffers but also turns out to work for replicators: Pick a small random seed pattern Simulate a moderate number of steps of a modified version of the cellular automaton rule, ...


7

Gil is asking if the GL is forgetting everything about its initial configuration in time independent of the size, when each cell "disobeys" the transition function independently of other cells with some small probability. To the best of my knowledge, this is not known for the GL. It is a very interesting question though. If it can withstand the noise, then ...


6

The main teams I know that study cellular automata are in the following laboratories (non-exhaustive list, probably biased towards french labs): LIAFA in Paris, France Université de Lorraine in Nancy, France LACL in Créteil, France University of Turku, Finland


6

The AUTOMATA workshop series focuses on cellular automata: http://www.eng.u-hyogo.ac.jp/eecs/eecs12/automata2014/


5

I underestimated the power of $C_3$ ... actually it is not too far from Hypercomputation! (I post this as a separate answer for better clarity) We can build a single state Turing machine $M$ that accepts the strings of the form: $L_Y = \{ a \; 0^n \; 1^m \; R \mid m \geq 2^n\}$ and rejects strings of the form: $L_N = \{ a \; 0^n \; 1^m \; R \mid m \lt ...


5

Yes, this problem is decidable in polynomial time. Let $R$ denote the term-rewriting system given by reductions of the form $$(r+s)\times(s+u)\longrightarrow(r\times s)+(s\times u).$$ Clearly, $R$ is strongly normalizing: indeed, each reduction step decreases the number of occurrences of $+$ in the term, hence any reduction sequence terminates after at most ...


5

If you are looking at North America, Jeffrey Shallit does research on the subject at the University of Waterloo.


4

From the comment: the undecidable questions are related to initial configurations with infinite support, whereas the conjecture refers to the behaviour of the ant when starting from a configuration with finite support (all but a finite number of cells are in the same initial state). If the conjecture is true then there are no undecidable problems starting ...


3

Look at the " $U$s " in the first table of the paper "Small Turing Machines ...". For example, 2 states and 18 symbols are enough to build a Turing Machine that can execute an operating system (if you augment it with an adequate I/O mechanism :) ... If you look for small models closer to the Von Neumann architecture then take a look at Random-access stored-...


3

For starters, keep in mind that research in Conway's Game of Life is still ongoing and future developments may present a far less complicated solution. Now then. Interestingly enough, this is a topic that is actually as much in line with biology and quantum physics as with traditional computer science. The question at the root of the matter is if any device ...


3

If South America is feasible for you, the Center for Mathematical Modeling at University of Chile has a fairly large and very active research group in symbolic dynamics and related fields, including cellular automata. Also, their emphasis is for the most part more mathematical than computer science-y.


3

Also, the MDSC team in I3S lab (http://i3s.unice.fr/), Nice, France


2

Edit: Please see the comments for why this does not address the question, however, I think I should not delete it in order to preserve the discussion... -- Not an expert, but my impression is that reversible computation does not by itself result in a change in entropy: the amount of information in the system has not changed, only the format in which it is ...


2

In this answer it is assumed that Turing machines have both-way infinite tapes. The claims do not hold for one-way infinite tapes. Let me first define the class of languages $C_3'$ as the class of all languages decidable by one-tape Turing machines with 3 states ($C_3$ was defined as the class of languages recognizable by one-tape Turing machines with 3 ...


2

The CONFIGURATION REACHABILITY PROBLEM: Given a cellular automaton and a pair of configurations $\langle X,Y \rangle$; does exist an instant $t \geq 0$ such that starting from configuration $X$, the cellular automaton reaches configuration $Y$ after $t$ iterations? is PSPACE-complete. If you drop $t$ from the input then you can achieve any r.e. degree of ...


2

There does indeed exist a category theoretic description of cellular automata. I don't know the details, but I can provide you with a reference. It doesn't look like an easy description, though. S. Capobianco, T. Uustalu. A categorical outlook on cellular automata. In J. Kari, ed., Proc. of 2nd Symp. on Cellular Automata, JAC 2010 (Turku, Dec. 2010), v. 13 ...


2

Judging from the source you provided, there appear to be two key differences: (1) stencils have numeric values in each cell and update the cells with functions defined numerically (typically using continuous functions) while cellular automata typically have only a finite set of values per cell and use functions that in general do not arise from numerical ...


2

the rule 110 initial condition constructions are extremely intricate even for simple computations and generally cannot be constructed by hand. one would generally start with a real/concrete TM [turing machine] built to compute your problem, ie the complete state table (TMs are of course alluded to in thousands of TCS papers but rarely actually built directly)...


Only top voted, non community-wiki answers of a minimum length are eligible