Introduction

Fix a flat three-dimensional torus, a positive viscosity, zero initial fluid velocity, one particle label, and an open region that serves as a detector. Can a finite program for an external force make that particle enter the region exactly when a given Turing machine halts? The machine and its finite input may change the force; the geometry, initial velocity, particle label and detector remain fixed. We prove this for an explicit family of smooth forces. The resulting reachability problem is undecidable.

The question connects computability with the dynamics of a continuous system. Turing proved that no machine can decide whether an arbitrary described machine ever prints a designated symbol [10]. The halting formulation used here follows by a finite modification that halts on that event. A bounded continuous phase space can represent such a tape by an infinite positional expansion. Moore’s generalized shifts made this connection explicit: local symbol changes and shifts of the tape become affine operations on real coordinates [7, 8]. Exact real coordinates supply the unbounded information capacity; this is not a bound on what a finite-precision measurement can recover.

A further issue arises when such operations are realized by a smooth flow. A machine may overwrite a symbol or merge two states, whereas the flow between two finite times is invertible. Retaining intermediate information is a classical way to avoid this loss [5]. Bennett gave an explicit reversible simulation that records the index of each executed instruction on a history tape [1]. Our construction uses the same information-retention principle in a different setting: a third real coordinate retains the selected branches, while two planar coordinates execute the original, possibly irreversible machine.

Computational universality has also been realized in fluid trajectories. Cardona, Miranda, Peralta-Salas and Presas constructed stationary Euler flows on an adapted Riemannian three-sphere whose trajectories simulate Turing machines [3]. Their proof passes through area-preserving realizations of generalized shifts. Dyhr, González-Prieto, Miranda and Peralta-Salas subsequently obtained stationary unforced Navier–Stokes universality using an adapted metric and Hodge viscosity [4]. Their velocity is harmonic for the chosen Hodge Laplacian, so the viscous term vanishes.

Fixed-metric computation also has precedents. Cardona, Miranda and Peralta-Salas construct universal steady Euler flows on Euclidean \(\mathbb R^3\) with infinite energy, and robust tape-bounded simulations on the flat three-torus, observed before exit from a prescribed compact region [2]. Their unforced viscous version starts from nonzero Beltrami velocity and traverses a finite interval of its Euler trajectory, chosen to cover the bounded computation [2].

Here the flat torus and viscosity are fixed in advance and the fluid starts at rest. The machine and input instead enter an external force prescription. These are different choices of data for the fluid equation, and the earlier results do not supply the construction below.

There is an elementary way to force a chosen smooth incompressible velocity: subtract its viscous term from its material acceleration. The mathematical work lies in choosing that velocity from the finite instruction table. It must execute each instruction, retain the information needed for invertibility, and avoid the detector at every intermediate time of a nonhalting run. In particular, our force formula must prescribe all instruction branches; it must not first execute the input computation and then replay its trajectory.

We implement an instruction in two pulses. The first records its branch number in the third coordinate. The second reads the newest record through a periodic gate and applies the corresponding planar motion. Earlier records remain present but do not affect that gate. As the history grows, the gates have finer spatial scales. We make successive steps longer so that the time-dependent velocity and force have square-integrable derivatives of every fixed order.

The result concerns exact material trajectories for these explicitly constructed forces. It gives neither a uniform perturbation tolerance for arbitrarily long runs nor an efficient simulation-time bound. Its existence and uniqueness proof uses the prescribed smooth velocity; it is not a regularity theorem for general Navier–Stokes data.

The statement and the history invariant

Write \(\mathbb T=\mathbb R/\mathbb Z\) and fix a positive computable viscosity \(\nu\). For velocity \(u(t,X)\), pressure \(p(t,X)\) and external force \(f(t,X)\), the incompressible Navier–Stokes equations are \[ \partial_tu+(u\cdot\nabla)u=-\nabla p+\nu\Delta u+f, \qquad \mathop{\mathrm{div}}u=0,\qquad u(0)=0 \tag{1}\] on the unit flat torus \(\mathbb T^3\). Pressure is periodic and has mean zero. We write \(X=(x,y,z)\) for a spatial point, use representatives in \([0,1)\) when specifying a coordinate interval, and take \(\|\cdot\|_\infty\) over space. The material flow of a smooth velocity \(u\) is defined by \[\frac{d}{dt}\Phi_u(t,a)=u(t,\Phi_u(t,a)),\qquad \Phi_u(0,a)=a.\] For a label \(a_*\in\mathbb T^3\) and an open set \(O\subset\mathbb T^3\), the particle event is \(\Phi_u(t,a_*)\in O\) for some finite \(t\).

An effective force prescription is a finite program that evaluates the force and any requested mixed derivative at computably supplied space-time arguments, to any prescribed rational error. It also supplies the derivative bounds on compact sets used below. The program prescribes the transition mechanism on all its branches; it does not compute and replay the distinguished execution. No running-time bound is required.

A classical competitor has continuous velocity, spatial derivatives through order two, time derivative, pressure and pressure gradient on every closed cylinder \([0,T]\times\mathbb T^3\), with the periodicity and pressure normalization above. The constructed solution is smooth, including all one-sided time derivatives at zero.

The proof has one particularly useful invariant. A branch specifies the current state and the symbols read by one local instruction; the precise list is given in Section 3. Number these finitely many branches by \(1,\ldots,J\) and put \(\Lambda=J+1\). If the first \(n\) selected branches are \(j_0,\ldots,j_{n-1}\), we will arrange \[ z_n=\sum_{i<n}j_i\Lambda^{-i-1}. \tag{2}\] Thus \(\Lambda^n z_n\) is an integer. Translating \(z\) by \(j_n\Lambda^{-n-1}\) makes its new value satisfy \[ \Lambda^n z=\frac{j_n}{\Lambda}\pmod 1. \tag{3}\] A smooth periodic gate can now select instruction \(j_n\). This is the continuous history record corresponding to the transition-index record in Bennett’s reversible simulation [1]. The earlier digits have become an integer and do not affect this gate. They have not been erased: they remain in \(z\), so two planar updates with overlapping images can still represent different pasts.

We next construct the planar branches and then realize (2) by a divergence-free field. The symbols \(j_n\) describe the trajectory in the proof; they will not occur in the formula for the force.

Here is the route through the proof. Section 3 converts each instruction into an area-preserving planar motion and proves that it cannot cause a false detection between nonhalting configurations. Section 4 combines the recorder and these motions into one smooth incompressible velocity, and proves the event equivalence. Section 5 chooses the force, establishes the derivative bounds and uniqueness, and verifies effective evaluation without running the machine. The Fourier projection there gives the optional solenoidal force.

A force that eventually stops changing in time poses a further question: its spatial mechanism must keep computing without progressively changing the gates. A separate companion gives that finite spatial mechanism and proves eventual stationarity [9]. The present proof uses the ordinary machine directly and requires no result from that companion.

The optional comparison theorem in Appendix 6.1 also applies on \(\mathbb R^3\) and \(\mathbb R^2\times\mathbb T\), with explicit Sobolev and pressure assumptions for other constructed flows. The particle theorem above concerns \(\mathbb T^3\) only. For a positive viscosity that is not assumed computable, the same formulas and estimates hold, with effective evaluation relative to the ability to approximate that fixed viscosity. Unqualified algorithmic assertions in this paper use the computable viscosity fixed above.

A machine instruction as a planar motion

Our task in this section is to turn each machine instruction into a planar motion whose entire path respects the detector. First encode the tape, then interpolate the resulting affine update by a Hamiltonian field.

First merge designated halting states into a single state \(q_h\), or adjoin an unreachable \(q_h\) if none is designated. Let \(Q\) now have \(N\geq1\) states, and let the tape alphabet \(\Sigma\) have \(m\geq1\) letters, including a blank \(\square\). Replace a missing instruction on symbol \(a\) by \((q_h,a,S)\), and give \(q_h\) stationary identity instructions. This finite normalization preserves the halting event, including an initially halted input. The tape is a sequence \((s_i)_{i\in\mathbb Z}\) in \(\Sigma\), with finitely many nonblank cells initially. Place the input word starting at cell zero, put blanks elsewhere, and start the head at zero in the machine’s initial state. Write \(\delta(q,a)=(q',b,D)\), where \(D\) is a left move, right move or stay.

The positional coding is the generalized-shift representation of a tape [8], with gaps inserted between symbol intervals. Give the letters the odd digits \(d_a\in\{1,3,\ldots,2m-1\}\) in base \(B=2m+1\), and set \[v(a_0a_1\ldots)=\sum_{r\geq0}d_{a_r}B^{-r-1}, \qquad I_a=[d_a/B,(d_a+1)/B].\] The intervals \(I_a\) are separated by gaps of length at least \(1/B\). A code lies in the interval of its first letter, and \(Bv(a\omega)-d_a=v(\omega)\) removes that letter. This proves unique decoding. A blank tail has value \(d_{\square}/(B-1)\), so all initial codes are rational.

If the head is at cell \(k\), encode the two relative tape halves by \[\ell=v(s_{k-1}s_{k-2}\ldots),\qquad r=v(s_ks_{k+1}\ldots).\] Put \(\kappa=(16N)^{-1}\) and \(y_0=3/8\). Enumerate nonhalting states as \(q_0,\ldots,q_{N-2}\) and choose \[c(q_i)=1/8+2i\kappa,\qquad c(q_h)=3/4.\] The planar code is \(P=(c(q)+\kappa\ell,y_0+\kappa r)\). The state box \([c(q),c(q)+\kappa]\times[y_0,y_0+\kappa]\) lies in \[K=[1/8,13/16]\times[3/8,7/16].\] Every nonhalting state box has \(x\leq1/4\); the halting box has \(x\geq3/4\). These inequalities leave room for a fixed detector between the two.

Index the triples \(j=(q,l,a)\) by \(1,\ldots,J=Nm^2\). Here \(a\) is the letter under the head and \(l\) the letter immediately to its left. Their closed source rectangles are \[R_j=(c(q)+\kappa I_l)\times(y_0+\kappa I_a).\] They are pairwise disjoint. If \(\ell_*=B\ell-d_l\) and \(r_*=Br-d_a\), the tape instruction is exactly \[ \begin{array}{c|cc} D&\ell'&r'\\ \hline R&(d_b+\ell)/B&r_*\\ L&\ell_*&[d_l+(d_b+r_*)/B]/B\\ S&\ell&(d_b+r_*)/B. \end{array} \tag{4}\] For example, a right move prefixes the written letter \(b\) to the left tape and removes \(a\) from the right tape. A left move removes \(l\) from the left tape and prefixes \(l,b\) to the old right tail. These operations explain both entries in each row of the table.

Let \(F_j\) be the resulting affine map in the physical coordinates \(P\). It maps the whole rectangle \(R_j\) into the next state box, and its linear part is \(\operatorname{diag}(\lambda_j,\lambda_j^{-1})\), with \(\lambda_j=B^{-1},B,1\) respectively. Different image rectangles may overlap. We will distinguish them by history, not by assuming that an ordinary machine is reversible.

We have obtained the correct endpoint update. We now realize it by a continuous motion, keeping every nonhalting-to-nonhalting path to the left of the detector. Local area-preserving realizations of bijective generalized shifts also occur in [3]; here a separate history coordinate will distinguish different branches with overlapping images.

Let \(C_j^0,C_j^1\) be the centers of \(R_j,F_j(R_j)\) and \(E_j=C_j^1-C_j^0\). For \(0\leq s\leq1\) define \[C_j(s)=C_j^0+sE_j,\quad g_j(s)=1-s+s\lambda_j, \quad \gamma_j(s)=\frac{\lambda_j-1}{g_j(s)},\] \[ \Psi_{j,s}(P)=C_j(s)+ \operatorname{diag}(g_j(s),g_j(s)^{-1})(P-C_j^0). \tag{5}\] This path starts at \(P\) and ends at \(F_j(P)\). Its first coordinate is the convex combination of the two endpoint coordinates. To control the second coordinate, let \(a\) be the source rectangle’s vertical half-width. Convexity of the reciprocal gives \[\frac{a}{g_j(s)}\leq(1-s)a+s\frac{a}{\lambda_j}.\] Together with the linear motion of the center, this keeps the entire rectangle in \(K\). In particular, an instruction with nonhalting source and target stays in \(x\leq1/4\) throughout its motion.

Choose a smooth cutoff \(\chi\) equal to one on a neighborhood of \(K\) and supported in the open unit square. Periodize the compactly supported Hamiltonian \[H_j(s,x,y)=\chi(x,y)\bigl[ E_{j,x}(y-C_{j,y}(s))-E_{j,y}(x-C_{j,x}(s)) +\gamma_j(s)(x-C_{j,x}(s))(y-C_{j,y}(s))\bigr].\] The planar field \(V_j=(\partial_yH_j,-\partial_xH_j)\) is divergence free and has mean zero. On the moving rectangle its components are \(E_{j,x}+\gamma_j(x-C_{j,x})\) and \(E_{j,y}-\gamma_j(y-C_{j,y})\). Differentiating (5) gives exactly these velocities. Uniqueness for the smooth ODE therefore shows that \(V_j\) realizes the claimed path, including its intermediate-time bound. The cutoff introduces no error there because all its derivatives vanish on that path.

Recording and selecting the instruction

Each instruction uses two pulses. The first reads the current source rectangle and adds its branch number to the history; the second uses that new digit to select the planar motion. Thus we can use the individual motions of Section 3 even when their planar images overlap. Figure 1 shows one step; the formulas below implement it simultaneously for every possible branch.

We specify the cutoffs to ensure that closed rectangle boundaries are covered. Let \[\rho(s)=\begin{cases}e^{-1/s},&s>0,\\0,&s\leq0,\end{cases} \qquad \sigma(s)=\frac{\rho(s)}{\rho(s)+\rho(1-s)}.\] For a closed interval \(I=[a,b]\), set \[\eta_I^\varepsilon(v)= \sigma\!\left(\frac{2(v-a+\varepsilon)}{\varepsilon}\right) \sigma\!\left(\frac{2(b+\varepsilon-v)}{\varepsilon}\right).\] The cutoff \(\eta_I^\varepsilon\) equals one on a neighborhood of \(I\) and vanishes outside its \(\varepsilon\) enlargement. Products define the analogous rectangle cutoffs. For the earlier Hamiltonians, choose \(\chi=\eta_K^{1/32}\); its support is strictly inside the unit square.

The source rectangles have gaps at least \(\kappa/B\), so the supports in \[G_0(x,y)=\sum_{j=1}^Jj\eta_{R_j}^{\kappa/(4B)}(x,y)\] are disjoint. Periodize this function from the unit-square chart and put \[G(x,y)=G_0(x,y)-G_0(x,y-1/2).\] The original supports lie in \(1/4<y<1/2\); their half-period translates miss every \(R_j\). Consequently \(G=j\) on \(R_j\) and \(G\) has zero mean. The correction permits a mean-zero vertical recorder without altering the tracked computation. Define the gates by periodizing the following bumps with period one: \[b_j(z)=\eta_{\{j/\Lambda\}}^{1/(4\Lambda)}(z), \qquad \Lambda=J+1.\] Their supports are disjoint and each equals one near its own center.

Let \(\theta(s)=\sigma(2s-1/2)\). It rises smoothly from zero to one inside \((0,1)\) and is constant near both endpoints. Set \[S_n=2^{n^2},\quad t_0=1,\quad t_{n+1}=t_n+2S_n, \qquad \alpha_n(t)=\frac{t-t_n}{S_n},\quad \beta_n(t)=\frac{t-t_n-S_n}{S_n}.\] Step \(n\) has a recorder interval and an equally long planar interval.

The initial planar code \(P_{\rm in}\) is rational. Let \(V_{\rm load}\) be the Hamiltonian field of \[\chi(x,y)[(P_{{\rm in},x}-1/8)y-(P_{{\rm in},y}-3/8)x].\] It translates \((1/8,3/8)\) along its straight segment to \(P_{\rm in}\). Define the velocity on \([0,\infty)\times\mathbb T^3\) by \[ \begin{split} U(t,x,y,z)={}&(\theta'(t)V_{\rm load}(x,y),0)\\ &+\sum_{n\geq0}\left( \frac{\theta'(\beta_n(t))}{S_n} \sum_{j=1}^J b_j(\Lambda^n z) V_j(\theta(\beta_n(t)),x,y),\quad \frac{\theta'(\alpha_n(t))}{S_n\Lambda^{n+1}}G(x,y) \right). \end{split} \tag{6}\] The displayed sum is a formula for all possible instructions. It has no reference to which instruction the machine will actually select.

At any time only one stage can be active. Since \(t_n\geq1+2n\), the sum is locally finite; the zero collars make every join smooth. Multiplying a planar divergence-free field by a function of \(z\) preserves its planar divergence, and the vertical component is independent of \(z\). Thus \(\mathop{\mathrm{div}}U=0\). Each planar field has zero planar mean, while \(G\) has zero planar mean, so \(U\) has zero spatial mean. Also \(U(0)=0\).

After the loader, the particle has planar coordinate \(P_{\rm in}\) and \(z_0=0\). Suppose at \(t_n\) it has the current planar configuration and history (2). It belongs to exactly one source rectangle, say \(R_{j_n}\). During the recorder interval its planar coordinate stays fixed, while integration of the last component in (6) adds \(j_n\Lambda^{-n-1}\) to \(z\). Equation (3) follows. On the planar interval only \(b_{j_n}\) is nonzero at this particle, and its value is one. Its path is therefore \(\Psi_{j_n,\theta(\beta_n(t))}(P(t_n))\), ending at the next machine code. The third coordinate stays fixed on this interval. This proves the induction and (2) for every \(n\).

There is no wraparound ambiguity for the tracked history: \(0\leq z_n\leq1-\Lambda^{-n}\). At a known step its finite radix expansion recovers every previous branch, hence every head displacement and the absolute head position. The planar coordinates recover the state and relative tape. This is an encoding of the computation, not merely a halting indicator.

If the machine halts, a planar code with \(x\geq3/4\) is reached after finitely many finite stages. If it is initially halted, the loader already reaches such a code. Conversely, for a nonhalting run the loader stays in \(x\leq1/4\), a recorder interval does not change \(x\), and (5) stays in \(x\leq1/4\) at every planar stage. This proves both directions of the event equivalence at every real time.

Slowing the gates and obtaining the force

The velocity now implements the machine and gives the correct event at every time. It remains to control its derivatives, realize it as the unique fluid velocity, and show that the force has a finite effective prescription.

Comparison on noncompact domains and Fourier identification

The main particle theorem is already complete. We record two analytic details separately: a comparison theorem with precise noncompact pressure assumptions, useful for other prescribed flows, and the elementary Fourier uniqueness argument used in the periodic projection.