# On Computational Hardness of Multidimensional Subtraction Games +
## 6 Parallel Execution of a Turing Machine  
In our plan of the proof (see Section 3), we simulate an operation of a specific Turing machine \(M\) on a specific input \(w\) by an operation of a 2 CA on the fixed starting configuration (as it described in the previous section). Thus we need yet another construction: a Turing machine \(U\) simulating an operation of a Turing machine \(M\)_on all inputs_. The idea of simulation is well-known, but again, we need to specify some details of the construction. We use notation from the previous section and assume that on each input of length \(n\) the machine \(M\) makes at most \(T(n)\) steps, where \(T(n)>n\). It is convenient to include in the alphabet of \(U\) the set \(A=\{0,\ldots,q\}\times\{0,\ldots,\ell\}\). Note in advance that there are some additional symbols in the alphabet. An operation of \(U\) is divided into _stages_ while its tape is divided into _zones_. Each zone is used to simulate an operation of \(M\) on a specific input \(w\). All the zones are placed between delimiters, say, \(\triangle\) and \(\triangleright\). In calculations below we assume that \(\triangleleft\) is placed in the cell \(0\). Also, the zones are separated by a delimiter, say, \(\diamond\). At the start of a stage \(k>1\) there are \(k-1\) zones corresponding to the inputs \(w_{1}\), \(w_{2}\),..., \(w_{k-1}\) of \(M\). We order inputs (i.e., binary words) by their lengths and words of equal length are ordered lexicographically. Each zone consists of three blocks. The blocks in a zone are separated by a delimiter, say \(\#\). They are pictured in Figure 2.  
Machine \(U\) maintains the following content in the blocks at the start of a stage \(k>1\). The content of the second block of a zone \(i\) specifies the input \(w_{i}\) of the machine \(M\). The size of the first block is \(1\). The cell in this block carries the symbol yes iff \(M\) accepts the input \(w_{i}\). Otherwise, it carries the symbol no. In this way we do not distinguish an unfinished computation and the negative result. However, it does not affect the correctness of reductions built on this construction. The last block of the zone contains a configuration of \(M\) after running \(k-1-i\) steps on input \(w_{i}\). In particular, the last zone contains the initial configuration on input \(w_{k-1}\). The configurations are represented by words over the alphabet \(A\), as described in Section 5. During the first stage, machine \(U\) writes on the tape the first zone containing the initial configuration on the input \(w_{1}\). The zone is surrounded by \(\triangleleft\) and \(\triangleright\). During the stage \(k>1\), machine \(U\) traverses the tape from the left delimiter \(\triangleleft\) to the right delimiter \(\triangleright\). Entering a zone, it simulates the next step of operation of \(M\) on the corresponding input. At the end of the stage machine \(U\) creates a new zone corresponding to the input \(w_{k}\) and the initial configuration of \(M\) on this input. The initial configuration is extended in both directions by white space of size \(T(n)\), see Figure 3.  
If the simulation procedure detects that the operation of \(M\) on an input \(w_{i}\) is finished, machine \(U\) updates the resulting block if necessary and it does not change the zone on the subsequent stages. In the arguments below we need \(U\) to satisfy specific properties. Figure 3: A fresh zone on the stage \(k\). Figure 2: A zone on the tape of \(U\). **Proposition 4**. : _If \(T(n)=C\cdot(n+1)^{2}\cdot 2^{n}\) for some integer constant \(C\geq 1\) then there exists \(U\) operating as is described above such that_  
1. _For all sufficiently large_ \(n\) _machine_ \(U\) _produces the result of operation of_ \(M\) _on the input_ \(w\) _of length_ \(n\) _in time_ \(<2^{4n}\)_._
2. _The head of_ \(U\) _visits the first blocks of zones only on steps_ \(t\) _that are divisible by_ \(3\)_._  
Proof. : At first, we show how to construct a machine \(U^{\prime}\) satisfying the property 1.