MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does there exist a Turing complete, cellular automata with universe and alphabet $\mathbb{Z}$ such that the only allowable configurations are permutations of $\mathbb{Z}$? Formally, consider $\tau : Sym(\mathbb{Z}) \to Sym(\mathbb{Z})$ satisfying the following property: there exist a finite subset $S \subset \mathbb{Z}$ and a function $\mu : \mathbb{Z}^S \to \mathbb{Z}$ such that

$\begin{aligned} \tau(\pi)(n) = \mu((\pi \circ L_{n}) |_{S}) \end{aligned}$

for all $\pi \in Sym(\mathbb{Z})$ and $n \in \mathbb{Z}$. Here $L_{n} : \mathbb{Z} \to \mathbb{Z}$ is defined by the rule $L_n(m) = n+m$. Can such a $\tau$ simulate a Turing machine?

share|cite|improve this question
up vote 1 down vote accepted

Yes, your permutation automata concept can simulate Turing machines.

You describe an update procedure $\tau$ that operates on a given permutation of $\mathbb{Z}$, let us imagine the permutation written out in a line, by local rearrangements: the new value at position $n$ is determined by the previous values in the size $|S|$ neighborhood of $n$. One "computes" with such an update procedure by starting from an input configuration that is regular in some way and then iteratively applying the update procedure until some halting feature is observed.

Such a kind of update procedure can encode the operation of a Turing machine and therefore is Turing complete (actually stronger than this, as I explain below). One way to do this would be as follows. Fix a given Turing machine $p$ with fewer than $k$ states for some large finite $k$. Divide the integers into finite blocks of size $k$; these will code the Turing machine cells of the computation of $p$ that we shall simulate. We shall only use permutations that operate on the intervals $I_n=[nk,(n+1)k)$, that is, they only move numbers around inside the blocks of the multiples of $k$. To mark the beginning of such a block $I_n$, we shall place $nk$ in the first position of $I_n$, and our update procedure will not move it. (This enables the update procedure to know where the blocks begin and end.) The next two positions in the block will hold the values $nk+1$ and $nk+2$, either in this order or reversed, in order to indicate the $0/1$ value of the cell that is being simulated. The remaining positions will hold the remaining values from $nk+3$ up to $(n+1)k$ arranged in such a way so as to indicate whether the Turing machine head is present on that cell and if so, what the state is. For example, if one of the values is out of order, then might indicate the presence of the head and the state. The point now is that the update procedure $\tau$ that would carry out the simulation of the program $p$ on these configurations is determined by looking only at the current block and the two adjacent blocks, to see if the head is coming in from the right or the left, and so it fits into your automata concept. Thus, we have a completely local update procedure in the manner you have described, and so your concept can simulate Turing machines.

But actually, your concept is far stronger than Turing machines. The reason is that your function $\mu$ is infinitary in nature, and not all such functions $\mu$ can be simulated by Turing machines. For example, there are continuum many different functions $\mu$, and one can prove that there will be continuum many different update procedures as a result. Thus, one should think about the situation rather as a oracle computation. The function $\mu$ is capable to simulating not only a Turing machine, but a Turing machine will an oracle tape, filled with information. Specifically, one may consider the update procedure that I describe above, but with the idea that an oracle tape is also simulated.

share|cite|improve this answer
Thanks Joel. This was very helpful. – James Reid Jul 6 '12 at 22:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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