Hardness of Approximation for Langton’s Ant on a Twisted Torus

Abstract

Langton’s ant is a deterministic cellular automaton studied in many fields, artificial life, computational complexity, cryptography, emergent dynamics, Lorents lattice gas, and so forth, motivated by the hardness of predicting the ant’s macroscopic behavior from an initial microscopic configuration. Gajardo, Moreira, and Goles (2002) proved that Langton’s ant is PTIME -hard for reachability. On a twisted torus, we demonstrate that it is PSPACE hard to determine whether the ant will ever visit almost all vertices or nearly none of them.

1. Introduction

In 1986, Chris Langton proposed an artificial life on square lattice $\mathbb{Z}\times \mathbb{Z}$ [1,2,3,4,5] where each vertex is either to-right (white) or to-left (black). An ant, represented by an arrow in Figure 1, travels along edges with unit speed and four possible directions. It turns to either right or left, corresponding to the vertex’s white or black color it is heading and switches the color simultaneously. Since then, it is one of the most widely studied cellular automata in many fields, for example, discrete propagation kinetics [6,7,8], Lorentz lattice gas [9,10,11], particle diffusion dynamics [12,13], computational complexity [14,15,16], emergent dynamics [17,18], and cryptography [19,20,21,22,23].

This paper’s motivation is the following chaotic trajectory of Langton’s ant. Placed on the all-white vertices, the ant stays within $45\times 48$ area for about 10,000 moves unpredictably, and then it suddenly starts dancing a highway of 104 steps drawn in Figure 2 and moving diagonally in speed $\sqrt{2}/52$ [13]. After decades of exploration, this phenomenon has been taking place with no exception, giving rise to a famous conjecture—the highway must eventually appear regardless of any initial configuration with finite support. If so, the ant’s long-run behavior is predictable except for reflection and transposition. Grosfils, Boon, Cohen, and Bunimovich [12] developed diffusion dynamics proving the highway conjecture and measuring the diffusion speed on triangular lattice. Meanwhile, Gajardo, Moreira, and Goles (GMG, [14]) constructed a finite configuration to evaluate a given boolean circuit. We note that these theoretical results fundamentally affected the related fields. For example, suppose that Langton’s ant is a particle system where a finite initial configuration and its consequent macroscopic quantities are the only observables. If highway conjecture holds, macroscopic observables are fixed constants regardless of the initial state. In any case, they must have some calculation from the initial finite configuration since the system is deterministic. GMG demonstrates that calculus PSPACE-hard if macroscopic quantities rely on an ant’s microscopic behavior called reachability.

This paper aims to strengthen GMG in both computational complexity and highway conjecture. Computational complexity measures time and space (memory) that modern computers, that is, Turing machines, must spend for solving a given computational problem (see computational complexity textbooks, for example, Reference [24]). GMG proved that the ant’s trajectory could simulate any computation spending a polynomial ($n^c$ for some constant $c\ge 1$) time for any bit-length n instance. GMG constructed a boolean circuit evaluator since circuit evaluation is a PTIME -complete problem, that is, simulating any polynomial-time calculation. Similarly, QCNF is a PSPACE -complete problem to execute any polynomial-space computation [25]. QCNF evaluates a given Conjunctive Normal Form (CNF) with bounded quantifiers. For example, QCNF evaluates $\forall x_1,\exists x_2,(x_1\vee \neg x_2)\wedge (\neg x_1\vee x_2)=$ TRUE, since for any $x_1\in$ {TRUE, FALSE}, there exists $x_2\in$ {TRUE, FALSE}, making the 2-term 2-variable CNF $(x_1\vee \neg x_2)\wedge (\neg x_1\vee x_2)=$ TRUE. PSPACE-complete problems take exponential time for any known algorithms, although P ≠ PSPACE is merely a conjecture. We note that GMG constructed a universal Turing machine but using an infinite number of black vertices for the initial configuration.

This paper aims to obtain the first result that the ant’s trajectory is unpredictable, even for a macroscopic measurement [3]. Let ${\mathbb{Z}}_n=\{-\lfloor \frac{n-1}{2}\rfloor ,\cdots ,-1,0,1,\cdots ,\lceil \frac{n-1}{2}\rceil \}$. For a coloring ${\theta }_n$ with black vertices in only ${\mathbb{Z}}_n\times {\mathbb{Z}}_n$, let $f_{{\theta }_n}(N,T)$ be the number of vertices in ${\mathbb{Z}}_N\times {\mathbb{Z}}_N$ that the ant starting from the origin will visit after T steps. We call ${\mathbb{Z}}_n\times {\mathbb{Z}}_n$ microscopic field, while ${\mathbb{Z}}_N\times {\mathbb{Z}}_N$ macroscopic one. If highway conjecture holds, we have $\forall \theta ={\left\{{\theta }_n\right\}}_n,{\rho }_1\left(\theta \right)=11/\sqrt{2}$ for ${\rho }_c\left(\theta \right):={lim}_{n\to \infty }{lim}_{N\to \infty }{lim}_{T\to \infty }{f}_{{\theta }_n}(N,T)/N^c$. However, we do not even know $\forall \theta ,{\rho }_2\left(\theta \right)<1$, that is, the ant may visit almost all vertices for some $\theta$. The only known previous result is $\forall \theta ,{\rho }_1\left(\theta \right)>0$, that is, the ant’s trajectory must always be unbounded [10]. Although ${\rho }_2\left(\theta \right)$ measures $N^2$-order convergence rather than more accurate N-order one required in highway conjecture, its impact is substantial on the related fields. For example, if $\forall \theta ,{\rho }_2\left(\theta \right)=0$, mathematical analysis may have a chance to prove highway conjecture on square lattice, as they have done in triangular lattice [9,12] and one-dimensional lattice [7,12]. If $\exists \theta ,{\rho }_2\left(\theta \right)=1$, cryptographic applications [19,20,21,22,23] may find finite configurations producing infinitely long pseudo-random bits generated by the ant’s trajectory.

This paper will show that ${\rho }_2\left(\theta \right)$ is hard to approximate on a twisted torus. A torus is the standard boundary condition to extend a coloring $\varphi$ on ${\mathbb{Z}}_N\times {\mathbb{Z}}_N$ to $\mathbb{Z}\times \mathbb{Z}$ by $\varphi (x,y)=\varphi (x+N,y)=\varphi (x,y+N)$ for $(x,y)\in \mathbb{Z}\times \mathbb{Z}$. Long-run computer simulation of square lattice cellular automata usually takes this topology [19,20,22]. An h-twist ($h/N$-pitch) of the torus is $\varphi (x,y)=\varphi (x+N,y)=\varphi (x+h,y+N)$. It appears in related models, for example, square-lattice Ising models (Langton’s ant is a typical one) [26,27]. When $h=\pm 11$, ${\rho }_2\left(\theta \right)=1$ may occur even under highway emergence, as described in Figure 3. For this specific case, we can prove the following theorem.

Theorem 1.

On ±11-twist torus, it is PSPACE hard to distinguish between ${\rho }_2\left(\theta \right)=1 and 0$

It states that modern computers cannot predict whether the ant on the twisted torus will ever visit almost all vertices or nearly none of them, even under the promise that either of these cases must occur. Notice that ${\rho }_2\left(\theta \right)$ is a time-independent measurement, counting the ever visiting vertices. Our proof will measure the period that an initial configuration of the cellular automaton appears again, too. Any closed loop of Langton’s ant’s propagating configurations must contain the initial one [6]. Let $g_{{\theta }_n}\left(N\right)$ be the period of Langton’s ant on ${\mathbb{Z}}_N\times {\mathbb{Z}}_N$ with an initial coloring ${\theta }_n$ on ${\mathbb{Z}}_n\times {\mathbb{Z}}_n$. Let ${\xi }_c\left(\theta \right):={lim}_{n\to \infty }{lim}_{N\to \infty }{g}_{{\theta }_n}\left(N\right)/N^c$.

Theorem 2.

On ±11-twist torus, it is PSPACE hard to distinguish between $({\rho }_2\left(\theta \right),{\xi }_2\left(\theta \right))=(1,\frac{208}{11})$ and $(0,0)$.

Consequently, no computer-aided analysis can calculate Langton’s ant’s macroscopic quantities from an initial finite configuration in polynomial time, unless P = PSPACE. We note that even under the (twisted) tours’s boundary condition, Lorentz lattice gas can measure the ant’s diffusion speed for triangular lattice [9], particle diffusion dynamics can do it for both triangular and one-dimensional lattices [12], and discrete propagation kinetics the diffusion speed or period of the ant’s rules for one-dimensional lattice [7]. Theorem 2 indicates that these currently known methods cannot measure them for square lattice.

A Proof Outline

Figure 4 reduces QCNF to Langton’s ant problem of distinguishment between $({\rho }_2\left(\theta \right),{\xi }_2\left(\theta \right))=(0,0)$ and $(1,\frac{208}{11})$. It maps a given QCNF instance $\Phi =\left\{{\Phi }_n\right\}$, say ${\Phi }_{n_0}=\forall x_1,\exists x_2,(x_1\vee \neg x_2)\wedge (\neg x_1\vee x_2)$ for a sufficiently large $n_0$ to encode it on ${\mathbb{Z}}_{n_0}\times {\mathbb{Z}}_{n_0}$, to a coloring $\theta (\Phi )=\left\{{\theta }_n\left({\Phi }_n\right)\right\}$ on microscopic field. The ant starting from the port (i.e., edge) S of TURN-A gate walks along a line and gets into the $G[\Phi ]$ chip (a collection of gates) at the entrance port I. The ant evaluates $\Phi$ and gets out from either the exit port F if it is FALSE or T if it is TRUE. In the former case, the ant reaches TURN-B gate. Since each TURN gate reverses the ant (i.e., putting the ant on the same port in the opposite direction), it must repeat a closed-loop between TURN-A and TURN-B gates due to time-reversibility; the reversed ant must travel back and rewind all steps it has taken in the time-reversing order. This loop holds the ant on microscopic field and thus makes a reduction $\Phi =\mathrm{FALSE}\Rightarrow \left({\rho }_2\left(\theta (\Phi )\right),{\xi }_2\left(\theta (\Phi )\right)\right)=(0,0)$. Similarly, the latter case induces another loop between TURN-A and TURN-C gates, passing through Hamiltonian-tour gate on the way, which drives the ant to visit almost all vertices in macroscopic field. It yields $\Phi =\mathrm{TRUE}\Rightarrow \left({\rho }_2\left(\theta (\Phi )\right),{\xi }_2\left(\theta (\Phi )\right)\right)=(1,\frac{208}{11})$, where $\frac{208}{11}=4/11·\sqrt{2}/(\sqrt{2}/52)$. Since these TURN gates take binary states flipping at the ant’s every visit, the ant travels Figure 3’s Hamiltonian-tour four times until revisiting the initial configuration. Each Hamiltonian-tour consists of $(N-O(n\left)\right)/11$ rounds of length-$\sqrt{2}N$ diagonals, taking $(N-O\left(n\right))/11·\sqrt{2}N/(\sqrt{2}/52)$ time since the ant’s speed is $\sqrt{2}/52$ [13].

Our previous paper [15] has already provided a coloring for the $G[\Phi ]$ chip to evaluate a QCNF formula $\Phi$, but using gray vertices at which the ant goes straight without changing the color [10]. Since it has permitted only a single gray vertex at each TURN gate and nowhere else, we are enough to exhibit only a new TURN gate with no gray vertex. However, open square lattice topology prohibits it because it tessellates the vertices of $\mathbb{Z}\times \mathbb{Z}$ into chess-board symmetry of $\{H,V\}$-polarity: Every H-vertex (resp. V-vertex) permits the ant to come Horizontally (resp. Vertically) and go vertically (resp. horizontally). Even-twist torus preserves $\{\mathrm{H},\mathrm{V}\}$-polarity, but odd-twist torus breaks it. If the ant living in odd-twist torus travels around vertically and comes back to the initial place, it can visit the world where every vertex possesses the opposite polarity. Figure 5 realizes a TURN gate in virtue of this polarity switching phenomenon. The ant enters at the port S, passing through FL (FLipper) gate, and reaching HW (HighWay) gate. The ant gets on Figure 2’s highway and travels towards a $\sqrt{2}N$ away destination place in a diagonal direction. The odd-twist torus’s topology brings the ant to a new world possessing the same address but the opposite polarity. Accordingly, after getting off the highway, the ant passes through the FL gate again and gets out the TURN gate from the same port S that it has entered but in the opposite direction.

A Hamiltonian-tour gate to visit almost all vertices is easy to realize: Let the ant get on a highway at the entrance port I of top-left $H_2$ in Figure 4. It brings the ant to a Hamiltonian tour along screwing diagonals of Figure 3: Each diagonal transports the ant by a horizontal and vertical distance N, bringing it back to the same address but a horizontal displacement $\pm 11$ due to the twisted torus topology. This gap number 11 fits the highway width, providing an exhaustive, mutually exclusive vertex cover. The highway must assume white color of the underlying vertices, so it remains at most $n^2$ vertices inside microscopic field unvisited. Figure 6 paves gates along the border between microscopic and macroscopic fields to generate consecutive multiple highways H₁, H₂, …, H₄ surrounding the $G[\Phi ]$ chip. The ant must pass through all these highways in order: It gets on each H_i at the entrance port I of Figure 6 placed in Figure 4’s left H_i, making a trip to the right H_i, getting off there at the exit port $O_2$, and walking along a line guiding to the next left H_i+1’s entrance port.

We follow an analysis of Reference [16] in making efficient embedding of Figure 4’s cellular automaton to the square lattice, although it allowed using gray color freely in CROSS gates. Reference [15] prohibits it there, but their CROSS gate was large and complex. This paper will maintain the efficiency of Reference [16] by providing a new construction of CROSS gate having size 9 × 9 in Figure 7.

2. Gates

A gate is a coloring on a limited lattice area for embedding the corresponding part of Figure 4’s cellular automaton to square lattice. This section describes the necessary gates composing all parts of Figure 4. These gates must endure repeated usage under contamination by the ant’s passage. Time reversibility of Langton’s ant recovers the initial state: The ant passes a gate by $I\to O$, that is, entering at I, staying inside the gate for a while, and finally exiting at O, changing the gate’s state $C\to D$. After that, the ant placed on $O^{-1}$, the same port O but the opposite direction, must proceed as $O^{-1}\to I^{-1}$ and changes the gate’s state as $D\to C$. We say that the ant’s inverse trip must charge the dry gate for the next passage.

Figure 8, Figure 9, Figure 10, Figure 11 and Figure 12 display gates and their state diagrams called Straight PATH, Bending PATH, JOIN (called CONJ in Reference [15]), S&P (Switch and Pass), and SWitch (SW in short), respectively. These state diagrams are Mealy machines outputting ant’s tracks when state transitions occur. When $C\to D$ occurs, the ant must travel from I to O inside the gate along the track (a series of the ant’s moves to either the Left (L) or Right (R) directions). We write it as $I\left[\mathrm{X}\right]\stackrel{C/D}{\to }O\left[\mathrm{X}\right]$ or $C\left[\mathrm{X}\right]\stackrel{I/O}{\to }D\left[\mathrm{X}\right]$. For example, PATH can stretch upwards by alternating Figure 8 with its H&D (H-symmetry and Dual, that is, flipping Horizontally and swapping C ↔ D), I[PATH] $\stackrel{I/O}{\to }$O[PATH] →I[H&D PATH] $\stackrel{I/O}{\to }$O[H&D PATH] →I[PATH] $\stackrel{I/O}{\to }$O[PATH] →⋯, forming a width-2 line, possibly bending to right by Figure 9. It can stretch and turn by 90 degrees to arbitrary directions by taking the symmetric and dual figures. PATH, S&P, and JOIN have the same configurations as Reference [15]. Differences from Reference [15] are parsing a S&T (Switch and Turn) gate in Reference [15] into three gates (SW, HW, FL) in Figure 5, providing a new TURN gate with no gray-color vertex, and a new CROSS gate having a much smaller size.

2.1. Turns

Figure 12, Figure 13 and Figure 14 present configurations of SW, FL, and HW, respectively. Any automatic method can check the correctness of these configurations. In Figure 14, the ant gets in HW at the entrance port I, passing through $I\to O_1$ for highway generation, riding on a highway propagation $O_1\to O_2$, and getting out of it at the exit port $O_2$ and walking away along a path starting from $O_2$. Figure 15 paves consecutive highways where each HW attaches an SW (horizontally flipped Figure 12) to share HW’s right-most two vertices with SW’s left-most ones. In this manner, Figure 4 paves the k TURNs ($G_1$ and $G_2$ with $k=2$ there) for the k variables of $\Phi$.

Lemma 1.

Every visit of the ant to Figure 5 induces $S\left[TURN\right]\to S^{-1}\left[TURN\right]$, accompanied by $C_F\left[SW\right]\stackrel{I_1/O}{\to }{C}_T\left[SW\right]$ (resp. $C_T\left[SW\right]\stackrel{O^{-1}/I_1^{-1}}{\to }{C}_F\left[SW\right]$) at each odd (resp. even) time visit.

Proof. 

In each odd time visit to Figure 5, the ant gets in from the entrance port S, travels along $S\to I\left[\mathrm{FL}\right]\stackrel{C_1{C}_2/D_1{C}_2}{\to }{O}_1\left[\mathrm{FL}\right]\to I\left[\mathrm{HW}\right]\stackrel{C_1{C}_2/D_1{C}_2}{\to }{O}_1\left[\mathrm{HW}\right]\underset{\to I_1\left[\mathrm{SW}\right]\stackrel{C_F/C_T}{\stackrel{}{\to }}O\left[\mathrm{SW}\right]\to }{\stackrel{D_1{C}_2/D_1{D}_2}{\stackrel{}{\to }}}{O}_2\left[\mathrm{HW}\right]{\to }^{*}{O}_2^{-1}\left[\mathrm{FL}\right]\stackrel{D_1{C}_2/D_1{D}_2}{\to }{I}^{-1}\left[\mathrm{FL}\right]\to S^{-1}$, and exits from the S it has entered but in the opposite direction. Here, the ant at ${\to }^{*}$ can get into the FL gate from the exit port $O_2$ since the ant lives in the opposite polarity world before and after taking the HW trip. Each even time visit induces the reversed travel $S\to I\left[\mathrm{FL}\right]\stackrel{D_1{D}_2/D_1{C}_2}{\to }{O}_2\left[\mathrm{FL}\right]\to O_2^{-1}\left[\mathrm{HW}\right]\underset{\to O^{-1}\left[\mathrm{SW}\right]\stackrel{C_T/C_F}{\stackrel{}{\to }}{I}_1^{-1}\left[\mathrm{SW}\right]\to }{\stackrel{D_1{D}_2/D_1{C}_2}{\stackrel{}{\to }}}{O}_1^{-1}\left[\mathrm{HW}\right]\stackrel{D_1{C}_2/C_1{C}_2}{\to }{I}^{-1}\left[\mathrm{HW}\right]\to O_1^{-1}\left[\mathrm{FL}\right]\stackrel{D_1{C}_2/C_1{C}_2}{\to }{I}^{-1}\left[\mathrm{FL}\right]\to S^{-1}$. Observe that the SW’s state has transited as claimed. □

2.2. Crosses

Figure 16 draws a state diagram of Figure 7’s CROSS gate constituting from 4 sub gates A–D; Figure 17, Figure 18, Figure 19 and Figure 20 show their configurations. It is automatic to check their correctness.

3. Lattice Embedding

A previous paper [16] transformed the $G[\Phi ]$ chip to a planar cellular circuit over {S&P, S&T, JOIN, CROSS} gates by Figure 21, Figure 22 and Figure 23 for $\Phi =\forall x_1,\exists x_2,(x_1\vee \neg x_2)\wedge (\neg x_1\vee x_2)$.

Lemma 2

([16]). A quantified CNF formula of k boolean variables, having m clauses, and ℓ occurrences of the literals can be computed by a planar cellular circuit having $k+\mathit{\ell }$ S&P, k S&T, $\mathit{\ell }-1+k$ JOIN, and $2{(\mathit{\ell }+m/2)}^2+9k$ CROSS gates.

The planar cellular circuit takes a classical Visual Representation (VR) [28,29] for square lattice embedding in Reference [16]. Notice that VR embedding have several aesthetic criteria, say draw edge as straight as possible, vertices should be evenly distributed, minimize bends in the lines. It represents each {S&P, JOIN, CROSS, SW, HW, FL} gate by a horizontal line segment and each path is connecting between them by a vertical line segment. Figure 7’s CROSS gate has size $9\times 9$ with just one port on each side, around which the ant can move by paths of width 2. Consequently, its VR embedding enjoys both horizontal and vertical sizes $9+2·2=13$.

Lemma 3.

Any cellular {S&P, JOIN, CROSS, SW, HW, FL}-circuit consisting of S CROSS gates and the other $o\left(S\right)$ gates have a VR embedding on ${\mathbb{Z}}_{(13+o(1\left)\right)S}\times {\mathbb{Z}}_{(8+o(1\left)\right)S}$.

Proof. 

VR embedding takes a height 13 to embed each CROSS vertex and a width 8 for the four lines of width-2 emitted from it. Since there are only $o\left(S\right)$ of the other kinds of vertices, the total height and width are no larger than $13S+o\left(S\right)$ and $8S+o\left(S\right)$, respectively. □

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\left(x\right)=T\left(x\right)$. 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,\dots ,x_k)\}}_{k\ge 1}$ such that $\forall k,\forall x\in {\{0,1\}}^k,L\left(x\right)=\Phi (x_1,\dots ,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 $c{s}^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 Φ of size $c{s}^2$ is transformable by a deterministic computation of $n^{O\left(1\right)}$ time and $O(logn)$ 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\le \underset{T\to \infty }{lim}{f}_{{\theta }_n}(N,T)\le N^2$ and $\frac{208}{11}(N^2-n^2)\le g_{{\theta }_n(\Phi )}\left(N\right)\le 208(\frac{1}{11}{N}^2+2^{c{s}^2}N)$, else $\underset{T\to \infty }{lim}{f}_{{\theta }_n(\Phi )}(N,T)\le \sqrt{n}N$ and $g_{{\theta }_n(\Phi )}\left(N\right)\le 208·2^{c{s}^2}N$.

Proof. 

Lemmas 2 and 3 embed the $G[\Phi ]$ chip to ${\mathbb{Z}}_{\tilde{n}}\times {\mathbb{Z}}_{\tilde{n}}$ for $s^4\ll \tilde{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}\left[\mathrm{TURN}-\mathrm{A}\right]\to I\left[G[\Phi ]\right]\stackrel{C/D}{\to }S\left[G[\Phi ]\right]\to S\left[\mathrm{TURN}-\mathrm{B}\right]\stackrel{C/D}{\to }{S}^{-1}\left[\mathrm{TURN}-\mathrm{B}\right]\to T^{-1}\left[G[\Phi ]\right]\stackrel{D/C}{\to }{I}^{-1}\left[G[\Phi ]\right]\to S\left[\mathrm{TURN}-\mathrm{A}\right]\stackrel{C/D}{\to }{S}^{-1}\left[\mathrm{TURN}-\mathrm{A}\right]\to \cdots \to S\left[\mathrm{TURN}-\mathrm{A}\right]\stackrel{D/C}{\to }{S}^{-1}\left[\mathrm{TURN}-\mathrm{A}\right]$. The ant visits only ${\tilde{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)\le {\tilde{n}}^2+k·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 takes at 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\left(s^4\right)$ gates and ${\tilde{n}}^2$ total path length, $g_{{\theta }_n}\left(N\right)\le 2^{k+2}·(52N+O\left(s^4\right)+{\tilde{n}}^2)\ll 208·2^{c{s}^2}N$.

If $\Phi$ is FALSE, $S^{-1}\left[\mathrm{TURN}-\mathrm{A}\right]\to I\left[G[\Phi ]\right]\stackrel{C/D}{\to }F\left[G[\Phi ]\right]\to H_1\left[I\right]\stackrel{C/D}{\to }{H}_1\left[O_2\right]\to \cdots \to H_j\left[I\right]\stackrel{C/D}{\to }{H}_j\left[O_2\right]\to S\left[\mathrm{TURN}-\mathrm{C}\right]\stackrel{D/C}{\to }{S}^{-1}\left[\mathrm{TURN}-\mathrm{C}\right]\to H_j\left[O_2^{-1}\right]\stackrel{D/C}{\to }{H}_j\left[I_2^{-1}\right]\to \cdots \to H_1\left[O_2^{-1}\right]\stackrel{D/C}{\to }{H}_1\left[I_2^{-1}\right]\to F^{-1}\left[G[\Phi ]\right]\stackrel{D/C}{\to }{I}^{-1}\left[G[\Phi ]\right]\to S\left[\mathrm{TURN}-\mathrm{A}\right]\stackrel{C/D}{\to }{S}^{-1}\left[\mathrm{TURN}-\mathrm{A}\right]\to \cdots \to S\left[\mathrm{TURN}-\mathrm{A}\right]\stackrel{D/C}{\to }{S}^{-1}\left[\mathrm{TURN}-\mathrm{A}\right]$. Here, $j\le \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. Consequently, $\underset{T\to \infty }{lim}{f}_{{\theta }_n}(N,T)\ge N^2-{\tilde{n}}^2>N^2-n^2$, and $g_{{\theta }_n}\left(N\right)>(N^2-n^2)·\frac{208}{11}$. An upper bound of $g_{{\theta }_n}\left(N\right)$ is the Hamiltonian tour time-bound $\frac{208}{11}{N}^2$ plus the $G[\Phi ]$’s evaluation $208·2^{c{s}^2}N$.

The only difference between Figure 4’s cellular automaton and the previous one in Reference [15] is parsing each k S&T gate inside Figure 22 and Figure 23 to Figure 5’s (SW, HW, FL) gates, and moving out both HW and SW to the outside but remaining the FL there. Observe that the SW gate entails three lines connecting I[SW]–$I_1$[JOIN], F[SW]-$I_1$[CROSS], and T[SW]–$I_2$[CROSS], and the HW gate two lines I[HW]–$O_1$[FL] and $O_2$[FL]–$O_2$[HW]. Each of these lines incurs 2 additional cross gates for preserving planarity through moving-out their gates outside of the k-times cascaded Figure 22 and Figure 23. Consequently, our cellular automaton may conttain $5·2·k(k-1)/2$ more cross gates than that in Lemma 2. The above analysis still holds even suffering this cross-gate incrementation. □

5. Conclusions

We have shown that it is PSPACE hard to predict whether the ant residing in h-twist torus will visit almost all vertices or nearly none of them, for $h=\pm 11$. We have embedded a closed QCNF $\Phi$ to ${\mathbb{Z}}_n\times {\mathbb{Z}}_n$ of the twisted torus ${\mathbb{Z}}_N\times {\mathbb{Z}}_N$ and measured the following quantities by dividing $N^2$ and taking the limit $N\to \infty$. If $\Phi$ is TRUE, then the density of ever visiting vertices is 1, and the period is $\frac{208}{11}$. Otherwise, both are 0. The same argument proves the following result for any odd number $h\ge 11$. Let $hmod11:=h-11\lfloor h/11\rfloor$. If $\Phi$ is TRUE, then the density is $1-\frac{\left|h\right|mod11}{\left|h\right|}$, and the period is $\frac{208}{11}·(1-\frac{\left|h\right|mod11}{\left|h\right|})$ since we have Figure 24’s screwing highway inserting $\left|h\right|mod11$ spaces between jth and $(j+1)$th diagonals for every $j\in \lfloor j/11\rfloor ·\mathbb{N}$. For example, for $\left|h\right|=23$, Figure 24 paves two consecutive screw highways $H_1$ and $H_2$ by Figure 6. For $\left|h\right|\in \{1,3,5,7,9\}$, we can prove that the ant’s reachability problem is PSPACE hard, since Figure 5’s TURN makes [15]’s PSPACE completeness proof valid. However, we have not yet found any non-zero density trajectory of Langton’s ant for $1\le \left|h\right|\le 10$. For every even number h, particularly the standard torus $h=0$, Langton’s ant’s known computational complexity is only the PTIME-hardness of Gajardo, Moreira, and Goles [14]. Proving PSPACE-hardness for even-twist torus is wide open.