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

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

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

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


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.


2

Consider the class of subshifts defined by a forbidden context-free language. For this class, equality and non-conjugacy are recursively inseparable, i.e. Theorem. There is no algorithm that given two context-free languages, says "same" if they define the same subshift, and says "non-conjugate" if they are not conjugate. Note that no requirement, even on ...


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 ...


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