# On Computational Hardness of Multidimensional Subtraction Games +
## 5 From Turing Machines to Cellular Automata
To define the transition function \(\delta_{M}^{(2)}\), we use a local inversion property of the encoding \(\varphi\): looking at the \(r\)-neighborhood of an \(i\)th bit of \(\varphi(c)\), where \(i=q(L+2)+k\), \(0\leq k<L+2\), one can restore symbols \(c(q-1)\), \(c(q)\), \(c(q+1)\), and position \(k\) of the bit provided the neighborhood contains zeroes (0 is the non-blank symbol of \(C_{M}^{(2)}\)). Let \(L=4\), \(r=12\). Assume that the neighborhood of the \(i\)-th bit, for some unknown \(i\), is  
\[11110011100011100011111.\]  
The series of three zeroes containing the \(i\)-th bit (underlined) is surrounded by ones. Therefore, it is a part of the symbol code \(\varphi(3)=110001\). It gives us a decomposition of the neighborhood into symbol codes:  
\[11\ 111001\ 110001\ 110001\ 1111.\]  
Thus, \(c(q-1)=2\), \(c(q)=3\), \(c(q+1)=3\), \(k=3\) (the fourth bit of the symbol code). Of course, we cannot restore the value \(q\) and the absolute position \(i\) of the bit. Please note that if the \(r\)-neighborhood of a bit does not contain zeroes then the bit is a part of encoding of the blank symbol 0 of \(C_{M}^{\prime}\) and, moreover, \(c(q-1)=c(q)=c(q+1)=0\). We generalize the arguments from the above example to prove the following fact. There exists a function \(\delta_{C}^{(2)}\colon\{0,1\}^{2r+1}\to\{0,1\}\) such that a \(2 CA\ C_{M}^{(2)}=(\{0,1\},\delta_{C}^{(2)})\) simulates \(C_{M}^{\prime}\): starting from \(b_{0}=\ldots 1110111\ldots\), it produces the sequence of configurations \(b_{0},b_{1},\ldots\) such that \(b_{t}=\varphi(c_{t})\) for any \(t\), where \((c_{t})\) is the sequence of configurations produced by \(C_{M}^{\prime}\) starting from the configuration \(c_{0}=\ldots 0001000\ldots\)  
Proof. : The function \(\delta_{C}^{(2)}\) should satisfy the following property. If \(b=\varphi(c)\) then  
\[\delta_{C}^{(2)}\big{(}(b(i-r),\ldots,b(i),\ldots,b(i+r)\big{)}=\varphi\big{(} \delta_{C}^{\prime}\big{(}c(q-1),c(q),c(q+1)\big{)}\big{)}(k) \tag{6}\]  
for all integers \(i=q(L+2)+k\), \(0\leq k<L+2\). This property means that applying the function \(\delta_{C}^{(2)}\) to \(b\) produces the configuration \(b_{1}=\varphi(c_{1})\), where \(c_{1}\) is the configuration produced by the transition function \(\delta_{C}^{\prime}\) from the configuration \(c\). Therefore, the sequence of configurations produced by \(C_{M}^{(2)}\) starting at \(\varphi(c_{0})\) is the sequence of the encodings of configurations \(c_{t}\) produced by \(C_{M}^{\prime}\) starting at \(c_{0}\). Please note that \(\varphi(c(q-1))\), \(\varphi(c(q))\) and \(\varphi(c(q+1))\) are in the \(r\)-neighborhood of a bit \(i\). Thus, from the condition on blank symbols in the alphabets \(A^{\prime}\) and \(\{0,1\}\), we conclude that the required property holds if the \(r\)-neighborhood of a bit \(i\) does not contain zeroes (non-blank symbols of \(C_{M}^{(2)}\)). In this case, the \(i\)th bit of \(b\) is a part of the encoding of the blank symbol 0 in the alphabet \(A^{\prime}\) and, moreover, \(c(q-1)=c(q)=c(q+1)=0\). Now suppose that the \(r\)-neighborhood of the \(i\)th bit contains zeroes. Take the nearest zero to this bit (either from the left or from the right) and the maximal series \(0^{q}\) containing it. The series is a part of the encoding of a symbol in \(c\). Therefore, there are at least \(1+L-a\) ones to the left of it. They all are contained in the \(r\)-neighborhood of the bit. Thus, we locate an encoding of a symbol \(c(q+q^{\prime})\), \(q^{\prime}\in\{-1,0,+1\}\), and we are able to determine \(q^{\prime}\). It depends on relative position of the \(i\)th bit with respect to the first bit \(j\) of the symbol located. If \(i-j\geq L+2\) then \(q^{\prime}=-1\); if \(L+2>j-i\geq 0\) then \(q^{\prime}=0\); otherwise, \(i-j<0\) and \(q^{\prime}=1\). Therefore, the symbols \(c(q-1)\), \(c(q)\), \(c(q+1)\) can be restored from the \(r\)-neighborhood of the \(i\)th bit. Moreover, a relative position \(k\) of the \(i\)th bit in \(\varphi(c(q))\) can also be restored.