A Fixed Particle Test for Computation in a Forced Viscous Flow

1 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, Section 8]. 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, Section 3]. Bennett gave an explicit reversible simulation that records the index of each executed instruction on a history tape [1, Eqs. (9)–(11)]. 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 \R^3 with infinite energy, and robust tape-bounded simulations on the flat three-torus, observed before exit from a prescribed compact region [2, arXiv version 3, Theorems 1 and 26]. 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, arXiv version 3, Remark 29].

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.

2 The statement and the history invariant

Write \T=\R/\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

on the unit flat torus \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

For a label a_*\in\T^3 and an open set O\subset\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\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

Thus \Lambda^n z_n is an integer. Translating z by j_n\Lambda^{-n-1} makes its new value satisfy

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 A.1 also applies on \R^3 and \R^2\times\T, with explicit Sobolev and pressure assumptions for other constructed flows. The particle theorem above concerns \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.

3 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\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, Section 1, Lemma 0], 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

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

Put \kappa=(16N)^{-1} and y_0=3/8. Enumerate nonhalting states as q_0,\ldots,q_{N-2} and choose

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

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

They are pairwise disjoint. If \ell_*=B\ell-d_l and r_*=Br-d_a, the tape instruction is exactly

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, Proposition 5.1]; 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

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

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

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.

4 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

For a closed interval I=[a,b], set

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

are disjoint. Periodize this function from the unit-square chart and put

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:

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

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

It translates (1/8,3/8) along its straight segment to P_{\rm in}. Define the velocity on [0,\infty)\times\T^3 by

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 \diver 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.

5 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.

5.1 Bounds for the prescribed velocity

Why choose the rapidly growing stage lengths S_n? Differentiating a gate b_j(\Lambda^n z) k times costs a factor \Lambda^{nk}. The factor S_n^{-1} in the velocity compensates for this at every fixed derivative order. More precisely, for a time order h and spatial multi-index \mu=(\mu_x,\mu_y,\mu_z), the fixed smooth profiles above give, throughout step n,

The profiles V_j and their phase derivatives are uniformly bounded for 0\leq s\leq1, because g_j(s)>0. The recorder has no z dependence and has an additional small factor \Lambda^{-n-1}, so it also satisfies this estimate. The constants depend on the finite table and derivative orders but not on n.

The right side of (7) is bounded, and integration over the two intervals of length S_n gives

The loader occupies a compact time interval and adds a finite amount. Now prescribe

Then (u,p)=(U,0) solves (1). Every mixed derivative of f is a finite sum of derivatives of U and products of two such derivatives. Each factor is bounded, and each has the stated temporal L^2 norm; use one bounded factor and one L^2 factor in a product. All force estimates in the theorem follow. Integration of (8) over the torus gives zero mean, because U has zero mean and (U\cdot\nabla)U=\diver(U\otimes U).

5.2 Uniqueness for the constructed torus flow

The residual identity gives the solution. We now show that its particle event is determined by the force and initial data. The proof is the classical difference-energy comparison [6, Section 18]. If (v,p) is another solution in the classical class of Section 2, set w=v-U. Subtraction gives

Multiplication by w and periodic integration by parts yield

The stated continuity of v_t, the first two spatial derivatives and pressure gradient justifies all these operations. The transport and pressure terms vanish by incompressibility. Boundedness of \nabla U on each finite interval and w(0)=0 give w=0 by Gronwall’s inequality. The equation then gives \nabla p=0, and mean-zero normalization gives p=0. Smoothness and bounded spatial gradient on the compact torus give a unique material flow through every finite time. Thus the event already proved for U belongs to the unique fluid solution. Appendix A.1 supplies the corresponding noncompact comparison theorem and the finite-time flow identities.

5.3 Solenoidal forcing with the same velocity

The Helmholtz–Leray projection removes the divergence of the force. Because it changes a gradient, it also changes the pressure. The following quantitative version is useful both for the present L^2 bounds and for other time profiles.

To apply Lemma 1 to the force in (8), we still need to verify its effective-evaluation hypotheses. The next subsection supplies them and completes the optional solenoidal construction. This periodic projection does not assert preservation of compact support on a Euclidean domain, nor does it preserve pressure zero.

5.4 Effective evaluation without a simulated execution

It remains to check that the prescription really is effective. We record the elementary fact about smooth profiles separately so that its computational hypothesis is explicit.

All tables, rational initial codes, affine maps and stage times are obtained from the finite input. Lemma 2 applies to their cutoffs and phase functions; the denominators g_j(s) have the effective positive lower bounds \min\{1,\lambda_j\}. The supports of \chi and the rectangle cutoffs lie in the rational coordinatewise enlargements of K by 1/32 and of R_j by \kappa/(4B), respectively. The unperiodized gate defining b_j is supported in [(j-1/4)/\Lambda,(j+1/4)/\Lambda]. Thus every periodization has the supplied support enclosure required by the lemma. For a time argument, obtain a rational upper bound T>t. The inequality t_n\geq1+2n gives a finite superset of possible active stages in (6); evaluating all of them is sufficient. Periodizations are evaluated by the same finite-superset procedure in coordinate charts, without deciding a real argument’s integer part. The Gaussian series above gives effective norm bounds: for example, if n\geq4\Lambda\mu_z, then \Lambda^{2n\mu_z}\leq2^{n^2/2}.

We may now apply Lemma 1 to f in (8). It gives an effective mean-zero solenoidal force f-\nabla\phi with solution (U,-\phi), the same derivative bounds, and the same particle event. The lemma’s pressure correspondence also transfers uniqueness from the original force. Riemann sums with derivative error bounds compute the Fourier coefficients, and the summable tail controls truncation. Neither this procedure nor the raw-force evaluation uses the branch sequence j_0,j_1,\ldots. For t\geq1 the loader and all its derivatives vanish, so the raw force depends on M and \nu but not on w. Its spatial projection at that time has the same independence. This completes the proof of Theorem 1.

A 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.

A.1 The precise comparison class

Let \Omega be \T^3, \R^3, or \R^2\times\T. A classical solution on [0,T] has continuous u, u_t, all spatial derivatives of u through order two, p, and \nabla p on the closed time cylinder, and satisfies the equation pointwise. In the noncompact cases we additionally require

The Sobolev spaces are periodic in the torus coordinates. On \T^3 the pressure has mean zero; on the noncompact domains its H^1 membership fixes the representative, since a nonzero spatial constant is not in L^2.

A.2 Identifying continuous periodic functions

A continuous function on \T^3 is determined by its Fourier coefficients. Here is the approximate-identity argument used in Lemma 1.

In one variable,

is nonnegative, has integral one, and has Fourier coefficients (1-|k|/N)_+. Outside any fixed neighborhood of the integers, the geometric-sum formula bounds F_N by C/N. Hence the product of three such kernels has mass tending to one in every neighborhood of zero. Uniform continuity shows that convolution with this product converges uniformly to any continuous function on \T^3. Vanishing Fourier coefficients therefore imply a vanishing function.