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?



Turing-Complete Cellular Automata and Sym(Z)
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.


