# On Computational Hardness of Multidimensional Subtraction Games +
## 5 From Turing Machines to Cellular Automata  
In this section, we describe how to simulate a Turing machine by a binary cellular automaton. It is standard, except for some specific requirements. Let \(M=(Q,\{0,1\},\Gamma,\delta_{M},1,2,3)\) be a Turing machine, where the input alphabet is binary, \(Q=\{1,\dots,q\}\), \(q\geq 3\) is the set of states, \(\Gamma=\{0,1,\dots,\ell\}\) is the tape alphabet, \(\ell>1\) is the blank symbol, \(\delta_{M}\colon Q\times\Gamma\to Q\times\Gamma\times\{+1,-1\}\) is the transition function, and \(1,2,3\) are the start, accept, and reject states, respectively. The tape of the machine assumed to be infinite in both directions. A configuration of \(M\) specifies the content of the tape, the position of the head and the state of the machine. We encode the configuration by a doubly infinite string \(c\colon\mathbb{Z}\to A\), where the set \(A=\{0,\dots,q\}\times\{0,\dots,\ell\}\) used to combine the content of a cell and the information about the head. Please note that \(0\
otin Q\). So, we assume that the head position is indicated by a pair \((q,a)\), \(q>0\), \(a\in\Gamma\); the content of any other cell is encoded as \((0,a)\), \(a\in\Gamma\). An operation of \(M\) starting from the configuration \(c_{0}\) generates a sequence of encoded configurations \(c_{0},\dots,c_{t},\dots\). It is easy to see that \(c_{t+1}(u)\) is determined by \(c_{t}(u-1)\), \(c_{t}(u)\), \(c_{t}(u+1)\). In other words, there is a function \(\delta_{\mathbb{C}}\colon A^{3}\to A\) such that \(c_{t+1}(u)=\delta\big{(}c_{t}(u-1),c_{t}(u),c_{t}(u+1)\big{)}\) for all \(u\) and \(t\geq 0\). Thus, the CA \(C_{M}=(A,\delta_{\mathbb{C}})\) over the alphabet \(A\) simulates the operation of \(M\) in encoded configurations. The symbol \(\Lambda_{\mathbb{C}}=(0,\ell)\) is the blank symbol: \(\delta_{\mathbb{C}}(\Lambda_{\mathbb{C}},\Lambda_{\mathbb{C}},\Lambda_{ \mathbb{C}})=\Lambda_{\mathbb{C}}\) (indeed, \(\ell\) is the blank symbol of \(M\), and \(0\) in the first coordinate indicates that the head is not over the cell). The next step is to simulate \(C_{M}\) by a 2 CA \(C_{M}^{(2)}\). The idea of simulation is simple: just a binary encoding of symbols from \(A\). But in the chain of reductions outlined in Section 3 we rely on specific features of the simulation. Therefore, we provide a detailed formal definition. Let \(C_{M}^{\prime}=(A^{\prime},\delta_{\mathbb{C}}^{\prime})\) be an automaton isomorphic to \(C_{M}\), where \(A^{\prime}=\{0,\dots,L-1\}\) and \(L=|A|=(|Q|+1)\cdot|\Gamma|\). The transition function \(\delta_{\mathbb{C}}^{\prime}\) of the automaton is defined as follows  
\[\delta_{\mathbb{C}}^{\prime}(i,j,k)=\pi(\delta_{\mathbb{C}}(\pi^{-1}(i),\pi^{ -1}(j),\pi^{-1}(k))),\]  
where \(\pi\colon A\to A^{\prime}\) is a bijection. To keep the relation between the start configurations, we require that \(\pi(\Lambda_{\mathbb{C}})=0\), \(\pi((1,\ell))=1\). Recall that \(1\) is the start state of \(M\) and \(\ell\) is the blank symbol of \(M\). The symbols of \(A^{\prime}\) are encoded by binary words as follows  
\[\varphi(a)=1^{1+L-a}0^{a}1.\]  
Thus, each symbol is encoded by a word of length \(L+2\). In particular, \(\varphi(0)=\varphi(\pi(\Lambda_{\mathbb{C}}))=1^{L+2}\) and \(\varphi(1)=\varphi(\pi(1,\ell))=1^{L}01\). The encoding \(\varphi\) is naturally extended to words in the alphabet \(A^{\prime}\) (finite or infinite). The extended encoding is also denoted by \(\varphi\). Thus, the start configuration of \(M\) with the empty tape corresponds to the configuration \(\dots 1110111\dots\) of \(C_{M}^{(2)}\). Recall that \(1\) is the blank symbol of \(C_{M}^{(2)}\). To construct the transition function of \(C_{M}^{(2)}\), we use the following alignment of configurations: if \(i=q(L+2)+k\), \(0\leq k<L+2\) then \(\varphi(c)(i)\) is the \((k+1)\)th bit of \(\varphi(c(q))\). The size of a neighborhood of \(C_{M}^{(2)}\) is \(r=2(L+2)\).