# Hardness of Approximation for Langton's Ant on a Twisted Torus
## 4 Hardness of Approximation for Langton's Ant  
We say that a function \(f:\{0,1\}^{*}\to\{0,1\}^{*}\) has a deterministic or non-deterministic computation of \(t\)-time and \(s\)-space if it has that kind of Turing machine \(T\) halting in \(t\) steps by using \(s\) walk-tape cells such that \(\forall x\in\{0,1\}^{*},f(x)=T(x)\). A language \(L:\{0,1\}^{*}\to\{0,1\}\) has a closed QCNF expression if there exists a sequence of closed QCNF expressions \(\{\Phi(x_{1},\ldots,x_{k})\}_{k\geq 1}\) such that \(\forall k,\forall x\in\{0,1\}^{k},L(x)=\Phi(x_{1},\ldots,x_{k})\); a closed QCNF is a QCNF with all \(k\) variables quantified. CNF's size sums the numbers of variables in the terms; QCNF's size is its CNF's size. **Theorem 3** ([25]). : _Let \(s\) be any integer larger than the number of input bits. Any language having a non-deterministic computation using \(s\) space admits a closed QCNF representation of size \(cs^{2}\) for some universal constant \(c>0\)._  
The next theorem demonstrates Theorems 1 and 2 by a reduction from the above theorem. **Theorem 4**. : _Let \(h=\pm 11\) and \(s^{4}\ll n\ll N\). A given closed QBF \(\Phi\) of size \(cs^{2}\) is transformable by a deterministic computation of \(n^{O(1)}\) time and \(O(\log n)\) space to a coloring \(\theta_{n}(\Phi)\) on \(\mathbb{Z}_{n}\times\mathbb{Z}_{n}\) of \(h\)-twist torus \(\mathbb{Z}_{N}\times\mathbb{Z}_{N}\), such that if \(\Phi=FALSE\) then \(N^{2}-n^{2}\leq\underset{T\to\infty}{\lim}f_{\theta_{n}}(N,T)\leq N^{2}\) and \(\frac{208}{11}(N^{2}-n^{2})\leq g_{\theta_{n}(\Phi)}(N)\leq 208(\frac{1}{11}N^{2}+2^{ \cos^{2}N})\), else \(\underset{T\to\infty}{\lim}f_{\theta_{n}(\Phi)}(N,T)\leq\sqrt{n}N\) and \(g_{\theta_{n}(\Phi)}(N)\leq 208\cdot 2^{\cos^{2}N}\)._  
Proof. : Lemmas 2 and 3 embed the \(G[\Phi]\) chip to \(\mathbb{Z}_{n}\times\mathbb{Z}_{n}\) for \(s^{4}\ll\bar{n}\ll n\) in the claimed time and space due to VR embedding algorithms [28; 29]. A previous paper [15] proved that if \(\Phi\) is TRUE (resp. FALSE), then the ant getting in \(G[\Phi]\)'s entrance port \(I\) must get out from the exit port \(T\) (resp. \(F\)). As explained by Figure 4 in Section 1, if \(\Phi\) is TRUE, the ant repeats \(S^{-1}[\text{TURN-A}]\to I[G[\Phi]]\xrightarrow{C/D}S[G[\Phi]]\to S[\text{TURN-B}] \xrightarrow{C/D}S^{-1}[\text{TURN-B}]\to T^{-1}[G[\Phi]]\xrightarrow{D/C} I^{-1}[G[\Phi]]\to S[\text{TURN-A}]\xrightarrow{C/D}S^{-1}[\text{TURN-A}]\xrightarrow{C/C}S^{-1}[\text{TURN-A}]\). The ant visits only \(\bar{n}^{2}\) vertices of the \(G[\Phi]\) chip plus \(11N\) of each HW gate for the \(k\) variables of \(\Phi\), yielding \(f_{\theta_{n}}(N,T)\leq\bar{n}^{2}+k\cdot 11N\ll N\sqrt{n}\). The ant switches the vaiables' values for \(2^{k+2}\) times since each of the four trips between TURN-A and TURN-B may consult at most \(2^{k}\) bit patterns to evaluate QCNF. Switching a variable takesat most \(52N\) steps for tripping HW in the TURN gate. Between them, the ant travels the same polarity, so each S&P, SW, and CROSS gate allow twice passages, and the other gates only once (see their state diagrams). Since the \(G[\Phi]\) chip contains at most \(O(s^{4})\) gates and \(\tilde{n}^{2}\) total path length, \(g_{\theta_{n}}(N)\leq 2^{k+2}\cdot(52N+O(s^{4})+\tilde{n}^{2})\ll 208\cdot 2^{cs^{2}}N\). If \(\Phi\) is FALSE, \(S^{-1}[\text{TURN-A}]\to I[G[\Phi]]\xrightarrow{\mathcal{L}/D}F[G[\Phi]] \to H_{1}[I]\xrightarrow{\mathcal{L}/D}H_{1}[O_{2}]\to\cdots\to H_{j}[I] \xrightarrow{\mathcal{L}/D}H_{j}[O_{2}]\to S[\text{TURN-C}]\xrightarrow{D/C}S ^{-1}[\text{TURN-C}]\to H_{j}[O_{2}^{-1}]\xrightarrow{D/C}H_{j}[I_{2}^{-1}] \to\cdots\to H_{1}[O_{2}^{-1}]\xrightarrow{D/C}H_{1}[I_{2}^{-1}]\to F^{-1}[G[ \Phi]]\xrightarrow{D/C}I^{-1}[G[\Phi]]\to S[\text{TURN-A}]\xrightarrow{ \mathcal{L}/D}S^{-1}[\text{TURN-A}]\to\cdots\to S[\text{TURN-A}]\xrightarrow{D/ C}S^{-1}[\text{TURN-A}]\). Here, \(j\leq\tilde{n}\) (\(j=4\) in Figure 4) is the number of Figure 6's HW gates surrounding the \(G[\Phi]\) chip, one of which (\(H_{2}\) in Figure 4) becomes a Hamiltonian tour.