GEOMETRIC PROGRAMS FOR SOLENOIDAL FORCING
(rewritten edition, for a first reading)
ABSTRACT
We build a smooth solenoidal force, periodic from time zero, on the flat
three-torus, for which one fixed particle hits one fixed open strip at
some finite time exactly when a given Turing machine halts. The initial
velocity and the pressure are zero. We also show how incompressible
motion realizes any finite list of positive diagonal maps between
separated rectangles: on thin sheets, where a change of planar area is
compensated by the normal direction, and on whole boxes of positive
thickness in the reciprocal case. Every construction is a finite list
of shears with explicit bounds on every intermediate position, so the
same formulas both define the force and prove what the particle does.
CONTENTS
0. How to read this paper; notation
1. The engine: transverse pulses
2. Shears, cutoffs, and tape codes
3. The recorder, and the proof of Theorem A
4. Other recorders, loaders, and charts
5. Whole boxes of positive thickness
6. Changing planar area: proof of Theorem B
7. The equation in material labels
8. Relation to earlier work, and what is different here
Appendix: one fixed interpreter
References
0. HOW TO READ THIS PAPER
0.1 The plan in one page.
Three ideas, in this order.
(1) A tape configuration becomes a point. Read the tape to the left of
the head as a number in base B, and the tape from the head onward as
another number. A finite set of machine rules then becomes a finite
list of rectangle-to-rectangle maps. Fixing the finitely many letters a
rule looks at gives a closed rectangle; the inverse of the rule shows
that the images of different rules are again separated rectangles.
This is Section 2.
(2) A rectangle map becomes fluid motion. Lift the source rectangle to
its own private height, deform it with four planar shears, translate it
to the target center, lower it. In every stage the velocity is
transverse: its nonzero component does not depend on the coordinate in
the direction it points. A transverse field has zero divergence and
zero self-advection, so f = u_t - nu Laplacian(u) gives a solenoidal
mean-zero force with pressure zero. This is Sections 1 and 3.
(3) An observer strip tests halting. Put all non-halting codes on the
left of the chart and all halting codes on the right. A fixed open
strip in between then contains a code exactly when the machine has
halted. Because the stages are timed and every intermediate position is
bounded, one checks that the particle cannot wander into the strip
during a step whose two ends are non-halting. This is the end of
Section 3.
The rest of the paper removes restrictions. Section 4 gives a recorder
that keeps the head marked (used in Section 5), a separate loader, and
other charts. Section 5 handles whole boxes rather than thin sheets.
Section 6 allows a planar map that changes area; volume preservation then
forces a compensating motion in the normal direction. Section 7 rewrites
the equation in material labels, Section 8 says what is new relative to
earlier work, and the appendix constructs one fixed interpreter, so that
the compiler may take either a machine table or just its input.
Nothing below needs measure theory, functional analysis, or PDE
existence theory. The only analytic input is the energy inequality for
two smooth solutions of the same forced Navier-Stokes equation, which is
three lines of calculus.
0.2 Notation.
R, Z, N are the reals, integers, positive integers. T^3_L = (R/LZ)^3
is the flat three-torus of side L, and T^3 = T^3_1. We write points as
(x,y,z) = (x_1,x_2,x_3), and e_1,e_2,e_3 for the standard basis. |v| is
the Euclidean norm, ||A|| the operator norm, ||g||_infty the supremum
norm, and div, grad, Laplacian the flat torus operators. All functions
on a torus are identified with their periodic lifts to R^3.
A rectangle is an axis-parallel product of intervals in the stated
coordinates. It is rational if all its endpoints are rational in a
fixed rational chart. A finite family of closed sets is positively
separated if the distance between any two distinct members is positive;
for finitely many disjoint closed rectangles this is automatic. A
geometric instruction is a triple (P,Q,F) where P,Q are closed
rectangles and F: P -> Q is an affine bijection. A list of geometric
instructions requires the sources to be pairwise separated and the
targets to be pairwise separated; nothing is assumed about a source
meeting a target.
A force prescription is effective if, given the finite data that
produced it (rational numbers and a machine table), every requested
mixed derivative at every requested rational space-time point can be
computed to any positive rational accuracy by a finite procedure. All
prescriptions below are finite sums of explicitly written smooth
profiles, so effectiveness is never in doubt; we mention it once.
0.3 The three theorems.
Theorem A (periodic compiler). Fix a computable viscosity nu > 0. Let
M be a deterministic one-tape machine with head moves in {-1,0,1}, and
let w be a finite input word. One can effectively construct a smooth
force f on T^3 such that:
(i) f is divergence free, has zero spatial mean, and is one-periodic
from time zero. The equation
u_t + (u.grad)u = -grad p + nu Laplacian(u) + f,
div u = 0, u(0,.) = 0,
has a global smooth solution with p = 0, and every classical solution
of that equation with zero initial velocity equals it.
(ii) u is one-periodic, vanishes near every integer time, satisfies
(u.grad)u = 0 at every time, has uniformly bounded kinetic energy, and
every mixed derivative of u and of f is globally bounded.
(iii) for the label a_* = (1/4, 1/2, 1/4) and the strip
O = {1/2 < x < 7/8}, the material trajectory X(t,a_*) enters O at some
finite time if and only if M halts on w, including the case that M
halts before moving.
The construction uses one Cartesian velocity component at a time. For
an arbitrary fixed real nu > 0 the same formulas hold and are effective
relative to nu.
Theorem B (diagonal maps on a sheet). Let P_i, Q_i, 1 <= i <= N, be
closed rational rectangles in [2,3]^2 with positive side lengths. Let
the sources be pairwise separated and the targets be pairwise separated,
and let F_i: P_i -> Q_i be the center-to-center affine map whose linear
part is an arbitrary positive rational diagonal matrix. For every
computable nu > 0 there is an effective smooth mean-zero solenoidal
force on T^3_10, one-periodic from time zero, whose solution has
pressure zero, velocity zero near integer times, zero self-advection,
bounded mixed derivatives, and period map
(y,2) |-> (F_i(y),2) for y in P_i.
No condition is imposed on source-target intersections. For N = 0 take
the zero field.
Theorem C (whole boxes). Let P_i, Q_i be closed rational rectangles in
the plane with positive side lengths at most one, separately separated
within each family, and let F_i be the center-to-center map with
reciprocal linear part diag(a_i, a_i^{-1}), a_i > 0 rational, mapping
P_i onto Q_i, fixing the third coordinate. Then there is a smooth
velocity, a finite list of pulses with disjoint time supports inside
[0,1], each pulse transverse and compactly supported in the coordinates
it depends on, such that the time-one map takes P_i x [-1/2,1/2] onto
Q_i x [-1/2,1/2] by the prescribed box map, all mixed derivatives are
bounded, and the following sign property holds: if a source and its
target both lie in x < 0, then that entire moving box stays in x < 0 for
all time. Scaling this velocity onto a torus and subtracting a
translated copy of each pulse produces a zero-mean solenoidal force with
the same trajectory statement; the proof in Section 5 spells both
steps out.
The proofs occupy Sections 1-6. Theorem A is proved in Section 3,
Theorem C in Section 5, Theorem B in Section 6.
1. THE ENGINE: TRANSVERSE PULSES
1.1 Transverse fields.
A vector field U on a torus is transverse if it has one of the forms
(U_1(y,z), 0, 0), (0, U_2(x,z), 0), (0,0, U_3(x,y)),
or the form (a(z), b(z), 0). In each case the nonzero components do not
depend on the coordinate in their own direction, so
div U = 0 and (U.grad)U = 0.
The second identity is the point: the material derivative of the
velocity of a transverse field vanishes, so the field moves fluid
without inertia. A sum of transverse fields need not be transverse,
because cross terms appear; therefore we never run two stages at once.
Each stage of every construction below occupies its own time interval,
and inside one stage all active pieces point the same way, so the sum is
still transverse.
1.2 The forcing lemma.
Lemma 1.1 (transverse pulses force their own motion). Let U be smooth
on [0,T] x T^3, with U(0,.) = 0 and with U(t,.) transverse for every t.
Put f = U_t - nu Laplacian(U) and p = 0. Then f is smooth, divergence
free and of zero spatial mean, and u = U solves the forced equation with
zero initial velocity.
Let v be any classical solution of the same equation with v(0,.) = 0,
on [0,T], and suppose sup over [0,T] of ||grad U|| is finite. Then v =
U and its normalized pressure is zero. Hence the solution is unique in
the classical comparison class.
The material flow of U exists for all finite forward times, is a smooth
diffeomorphism of the torus, and preserves volume. If a finite list of
pulses is repeated with period one and with zero collars at the joins,
then every mixed derivative of u and f is globally bounded and the
kinetic energy is uniformly bounded. The same conclusions hold when one
separate finite loading interval is put in front.
Proof. At each time div U = 0 and (U.grad)U = 0, so substituting
(u,p) = (U,0) gives U_t = -grad 0 + nu Laplacian(U) + f. Divergence
commutes with t-derivatives and with the Laplacian, and a periodic
Laplacian has zero integral, so f is solenoidal with zero mean.
For uniqueness put w = v - U. Subtracting the two equations gives
w_t + (v.grad)v - (U.grad)U = -grad p + nu Laplacian(w),
and (v.grad)v - (U.grad)U = (v.grad)w + (w.grad)U. Take the inner
product with w and integrate over the torus. The pressure term dies
because div w = 0, the term (v.grad)w dies after integration by parts
for the same reason, and the viscous term is -nu ||grad w||_2^2 <= 0.
Thus
(1/2) d/dt ||w||_2^2 + nu ||grad w||_2^2
<= ||grad U||_infty ||w||_2^2 .
Drop the nonnegative viscous term and apply Gronwall with w(0) = 0.
Then w = 0, so grad p = 0, and the normalization makes p = 0. Note what
was and was not proved: this compares two solutions of one explicitly
given force; it says nothing about arbitrary initial data.
For the flow, the periodic lift of U is bounded and Lipschitz on [0,T],
so trajectories exist, are unique, and continue for all finite time;
backward integration gives their inverses, and smooth dependence on the
initial point gives smooth diffeomorphisms. With M = D_a X, the chain
rule gives dM/dt = (grad U)(t,X) M, hence d(det M)/dt = div U (t,X) det M
= 0 and det M = 1, which is volume preservation.
Finally a repeated finite pulse list has finitely many phase templates.
Each template is a fixed smooth field on the torus, and the time
dependence is a fixed smooth pulse inside a fixed interval, so the
suprema of all mixed derivatives over one period bound them for all
time; the same holds for the force. The L^2 norm of the velocity is
bounded by the maximum over the finitely many templates. A single
additional loading interval adds one more template. []
1.3 Slowing time without losing anything.
Replacing t by a clock g(t) stretches a periodic construction into a
non-periodic one. To keep the same reachability question we need g to
be onto, so that every logical time is still reached.
Lemma 1.2 (onto clocks). Let W(s,x) be smooth, divergence free, of zero
mean, with W(0,.) = 0 and (W.grad)W = 0, and with bounded mixed
derivatives. Let g: [0,infinity) -> [0,infinity) be smooth,
nondecreasing and onto, with g(0) = 0. Put
u(t,x) = g'(t) W(g(t),x),
f(t,x) = g''(t) W(g(t),x) + (g'(t))^2 W_s(g(t),x)
- nu g'(t) Laplacian(W)(g(t),x).
Then f is smooth, solenoidal and of zero mean, and (u,0) solves the
equation with u(0,.) = 0. The material flow of u is
X_u(t,a) = X_W(g(t),a),
so a material trajectory enters a fixed open set at some finite real
time if and only if the underlying trajectory enters it at some finite
logical time.
For g(t) = log(1+t) and all k, alpha,
|| d_t^k D^alpha u (t) ||_infty + || d_t^k D^alpha f (t) ||_infty
<= C_{k,alpha} (1+t)^{-1-k},
and all these derivatives are square integrable in time in supremum
norm.
Proof. Divergence, zero mean and vanishing self-advection are
unchanged by multiplying by the scalar g'(t) and composing in time; a
direct differentiation gives f = u_t - nu Laplacian(u). The trajectory
identity follows from uniqueness of solutions of the ODE defining the
flow. Since g is onto, the sets of reached times correspond exactly.
For the logarithm write a = (1+t)^{-1} and s = log(1+t). Then
u = a W(s) and f = -nu a Laplacian(W)(s) + a^2 (W_s - W)(s). For every
positive integer r,
d_t [ a^r A(s) ] = a^{r+1} (d_s - r) A(s),
so each time derivative costs one factor a and at most one derivative in
s, and the boundedness of the templates gives the displayed bound. Its
square is integrable in t. []
Proposition 1.3 (power clocks). Under the hypotheses of Lemma 1.2 let
g(t) = (1+t)^q - 1 with q = 1/3 or q = 1/4, and put beta = 1-q. Then u
and f have bounded mixed derivatives and
|| d_t^k D^alpha u (t) ||_infty + || d_t^k D^alpha f (t) ||_infty
<= C_{k,alpha} (1+t)^{-beta-k},
and each such derivative is square integrable in time in supremum norm.
Proof. Each derivative g^{(j)} with j >= 1 equals a constant times
(1+t)^{-beta-j+1}, hence is bounded and decays like (1+t)^{-beta}. A
k-fold time derivative of g'(t) W(g(t),x) is a finite sum of products of
derivatives of g with derivatives of W evaluated at g(t); every term
contains at least k+1 derivatives of g, so it decays at least like
(1+t)^{-beta-k}, and the remaining factors are bounded. The identity
f = u_t - nu Laplacian(u) gives the same for f, and 2(beta+k) > 1. []
The slowed force is a different prescription from the periodic one.
One cannot have both exact period one and decay: a periodic nonzero
force does not decay. Nor can one slow down faster than quadratically
in an accumulated sense: if g' were bounded by C(1+t)^{-2}, the total
logical time elapsed would be finite, and a machine needing more steps
would never finish. The onto condition is exactly what rules this out.
2. SHEARS, CUTOFFS, AND TAPE CODES
2.1 The two elementary shears and three usable lists.
Write
X(a)(x,y) = (x + a y, y), matrix [[1, a],[0, 1]],
Y(a)(x,y) = (x, y + a x), matrix [[1, 0],[a, 1]].
A composition of shears is read right to left: the first shear applied
sits on the right of the matrix product. Each shear fixes one
coordinate and slides the other by an affine function of the fixed one,
so a shear field is transverse.
The reciprocal diagonal matrix diag(r, 1/r) can be written as a product
of four shears in many ways. Three lists will be used; all products are
taken in the reverse of the chronological order, and all equal
diag(r, 1/r) for rational r > 0:
list (a): Y(-r), X(1/r - 1), Y(1), X(r - 1),
list (b): Y(-r(r-1)), X(-1/r), Y(r - 1), X(1),
list (c): X(1/r - 1), Y(1), X(r - 1), Y(-1/r).
Lemma 2.1 (the three products). Each of the three lists, composed in
the stated order, equals diag(r, 1/r).
Proof. Multiply. For list (a), starting from the right,
X(1/r - 1) Y(-r) = [[r, 1/r - 1],[-r, 1]],
Y(1) times that = [[r, 1/r - 1],[0, 1/r]],
X(r - 1) times that = [[r, 0],[0, 1/r]].
For list (b),
X(-1/r) Y(-r(r-1)) = [[r, -1/r],[-r(r-1), 1]],
Y(r - 1) times that = [[r, -1/r],[0, 1/r]],
X(1) times that = [[r, 0],[0, 1/r]].
For list (c),
Y(1) X(1/r - 1) = [[1, 1/r - 1],[1, 1/r]],
X(r - 1) times that = [[r, 0],[1, 1/r]],
Y(-1/r) times that = [[r, 0],[0, 1/r]].
[]
Two bounds control where a point can be during these motions. Fix
B >= max(r, 1/r, 1). The operator norm of X(a) and of Y(a) is 1 + |a|.
Lemma 2.2 (crude excursion bound). Suppose |a_j| <= B for the four
coefficients of a list and the starting offset from the center of the
source rectangle satisfies |v| <= ell/2. Then at every intermediate
stage of list (a) or list (c) the offset from the source center is at
most (1+B)^4 ell/2, and for list (b) at most (1+B^2)^4 ell/2.
Proof. The offset after j shears is Z_j ... Z_1 v, whose norm is at
most the product of the operator norms times |v| <= ell/2. In lists (a)
and (c) every coefficient has modulus at most B. In list (b) the four
coefficients are r(r-1), 1/r, r-1, 1, so the four factors are at most
1 + B^2, 1 + B, 1 + B, 1 + B, and each of these is at most 1 + B^2
because B >= 1. []
The crude bound grows with B, which is bad, because the base of the tape
code must be large. List (a) admits a better bound that does not see r
at all, using both ends of the instruction.
Lemma 2.3 (endpoint-size excursion bound). Consider list (a) applied
to a source rectangle of half-width at most ell/2 whose image has
half-width at most ell/2. Then every intermediate point of the list is
within 3 ell/2 of the source center.
Proof. Let the starting offset be (xi, eta). The hypothesis at the two
ends says
|xi| <= ell/2, |eta| <= ell/2, |r xi| <= ell/2, |eta/r| <= ell/2.
The four intermediate offsets, computed by applying the shears in
order, are
z1 = (xi, eta - r xi),
z2 = (r xi + (1/r - 1) eta, eta - r xi),
z3 = (r xi + (1/r - 1) eta, eta/r),
z4 = (r xi, eta/r),
and z4 is the target offset. Each of these has norm at most
ell/2 + ell/2 + ell/2 = 3 ell/2: for z1 and z2 the second coordinate is
bounded by |eta| + |r xi|, and the first coordinate of z2, z3 is bounded
by |r xi| + |eta| (using |1/r - 1| <= 1 for r >= 1; the case r < 1 is
the same after swapping the roles of the two coordinates and reading
the list backwards). A partial pulse applies shear coefficients that
interpolate between zero and the listed values, so every intermediate
point lies on the segment joining two of the displayed points. []
2.2 Flat profiles with zero mean.
Here are the only profiles used later. Put
E(s) = exp(-1/s) for s > 0, E(s) = 0 for s <= 0,
H(s) = E(s) / (E(s) + E(1-s)).
Then H is smooth and nondecreasing, H(s) = 0 for s <= 0, H(s) = 1 for
s >= 1, and H(s) + H(1-s) = 1. For an interval I = [a,b] and a collar
delta > 0 put
chi_{I,delta}(s) = H(2(s - a + delta)/delta) H(2(b + delta - s)/delta).
This equals one on [a - delta/2, b + delta/2], is supported in
[a - delta, b + delta], and is symmetric about the midpoint of I.
Products of such factors give box cutoffs.
Two facts make these profiles safe for an effective construction.
First, every derivative of E on s > 0 is a polynomial in 1/s times
E(s), and E(s) <= n! s^n for every n, so all derivatives of E, H and
chi vanish at the edge of the support to every order. Second, the
denominator of H is at least exp(-2) on [0,1], because one of E(s),
E(1-s) is at least exp(-2). Hence every derivative of every profile is
bounded by an explicitly computable rational, and no computation ever
has to decide whether a point sits exactly on the edge of a support:
the profile is infinitely flat there.
Three recipes produce the zero-mean selectors used in the stages. In
all of them the selector must equal a prescribed affine function on a
neighborhood of every tracked path, and must integrate to zero.
(1) Derivative recipe. If chi_P is a box cutoff equal to one on a
neighborhood of a rectangle P and c = (c_x,c_y), then
partial_x ((x - c_x) chi_P(x,y))
equals 1 on the inner plateau and has zero mean, being a derivative on
the torus. Likewise partial_z ((z - z_i) zeta_i(z)) equals 1 near
z_i. This recipe needs a genuine neighborhood of the plateau, because
a derivative is taken.
(2) Translated-copy recipe. If the translate of the support of chi_P
by a vector delta misses P and all other tracked rectangles, then
chi_P(x,y) - chi_P(x,y - delta)
equals 1 near P and has zero mean, because the torus integral of a
translated function equals the original integral. No derivative is
taken, so no plateau neighborhood is needed, only the explicit
separation from the translated support.
(3) Odd-bump recipe. Let D < L/2 and let Xi_c be the L-periodic
function that equals (s - c) H(2 - 2(s-c)^2/D^2) for |s - c| < D and
zero for D <= |s - c| < L/2. It is odd about c, so its mean is zero;
it equals s - c on |s - c| <= D/2, where the argument of H is at least
3/2. Its derivative equals 1 there and also has zero mean. The same
construction with (1/2)(s-c)^2 in place of (s-c) gives a quadratic
profile whose derivative is the linear one.
2.3 Tapes as points: positional coding.
A relative tape is a bi-infinite sequence T = (T_j) indexed by Z, whose
index zero is the current head position. A full cylinder fixes a mode
and finitely many tape letters and lets every other letter be
arbitrary. Let the alphabet have m letters, choose a base B and
injective digits d(letter) in {0,1,...,B-2} whose distinct values
differ by at least two; typically B = 2m+1. For a finite word v put
C(v) = sum_{j>=1} d(v_j) B^{-j},
I(v) = [ C(v), C(v) + B^{-|v|} ].
The two coordinates of a relative tape are
L = C(T_{-1} T_{-2} ...), R = C(T_0 T_1 ...).
Place each mode in its own translated square of side ell and use (L,R)
as coordinates inside the square. This is the positional coding of
Moore; the following lemma is the only property we need.
Lemma 2.4 (full cylinders give full rectangles). Suppose a finite
injective partial map on tapes is partitioned into full cylinders, each
fixing a mode and the tape window [-a, b-1]. A branch reads that
window, writes a new window, and shifts by d, with a + d >= 0 and
b - d >= 0. Then each image is again a full cylinder, with rewritten
prefix lengths a + d and b - d, and the exact map on the whole closed
rectangle has linear part diag(B^{-d}, B^d). The closed source
rectangles are pairwise separated within their family, and so are the
closed target rectangles.
Proof. A prefix v followed by an arbitrary tail has code
C(v) + B^{-|v|} t with t in [0,1], so I(v) is a closed interval and the
tail parameter is free. The tails outside the window survive the edit
and the shift, so the image of a whole cylinder is the rectangle
I(new left prefix) x I(new right prefix), with the two prefix lengths
a + d and b - d; on the full rectangle the tail parameters are rescaled
by B^{-d} in the first coordinate and B^{d} in the second, which is the
stated linear part.
For separation, take two distinct cylinders of one mode. If both their
left prefixes were compatible and both their right prefixes were
compatible, some tape would belong to both cylinders, contradicting
disjointness; so at least one pair of prefixes is incompatible. Two
incompatible words w, w' of length n sharing the letters before the
first difference have C(w') - C(w) at least 2 B^{-j} at that position
j, while their intervals have length B^{-n} <= B^{-j}; hence the
intervals have a positive gap, at least B^{-n} in one coordinate. The
same argument applies to the images, using injectivity: distinct
sources have distinct images, and the images are full cylinders. The
modes themselves occupy separated squares by construction. []
Lemma 2.5 (one-cell rules in coordinates). For a rule that reads a,
writes b and moves by d, with T_a(v) = (d(a) + v)/B and I_a = T_a([0,1]),
the source and target rectangles and the coordinate formulas are
d = +1: source [0,1] x I_a,
(L', R') = (T_b(L), T_a^{-1}(R)), target I_b x [0,1];
d = 0: source [0,1] x I_a,
(L', R') = (L, T_b T_a^{-1}(R)), target [0,1] x I_b;
d = -1: source I_c x I_a for every letter c,
(L', R') = (T_c^{-1}(L), T_c T_b T_a^{-1}(R)),
target [0,1] x T_c(I_b).
Proof. Read the definitions of L and R. For d = +1 the new zero index
is the old index 1, so R' = C(old T_1 T_2 ...) = T_a^{-1}(R) while the
new left word begins with the written letter b, giving L' = T_b(L). For
d = 0 nothing shifts, so L' = L and only the written letter changes,
giving R' = T_b T_a^{-1}(R). For d = -1 the new zero index is the old
index -1, which held the letter c; the new left word is the old left
word without c, giving L' = T_c^{-1}(L), and the new right word begins
with c then b, giving R' = T_c T_b T_a^{-1}(R). The images are the
stated rectangles for the same reason as in Lemma 2.4. []
Lemma 2.5 also gives the inverse test used later, in words rather than
matrices: the target mode determines the incoming move, and the target
mode together with the written letter determines the previous mode and
letter. Deterministic rules give disjoint sources; the inverse test
gives disjoint targets. If the mode squares have gaps at least ell,
all within-family gaps are at least ell/B^2 in one coordinate.
3. THE RECORDER, AND THE PROOF OF THEOREM A
3.1 Conventions for machines.
A machine in this section has one two-sided tape, a finite alphabet with
a blank, a finite set of states, and for each state-symbol pair at most
one instruction (next state, written symbol, head move in {-1,0,1}).
Before we use it, normalize it as follows.
(a) Delete all instructions at halt states, so a halt state has no
outgoing instruction.
(b) At every non-halting state and every symbol with no instruction,
add one instruction: write the same symbol back, do not move, and go
to one fresh halt state which has no outgoing instructions.
This keeps the halting question: the machine halts at step n exactly
when it has no instruction, and a run that was already halting stays so
after zero steps. A partial table is a set of rows; an unlisted pair
means "no rule".
(c) If we want to guarantee at least one step, add one fresh state q_b
with, for each tape symbol, one instruction that writes the same
symbol, does not move, and goes to the original start state. No rule
goes into q_b. This adds one simulated step and changes nothing else;
even a machine that halts immediately now takes one step first.
A code point of a machine configuration is a point of a rectangle
constructed as in Section 2: read the tape to the left of the head
(nearest first) as one base-B number, the tape from the head on (nearest
first) as another, and put the pair inside the mode square of the
current state. All codes of a finite run are rational numbers, since
only finitely many cells differ from blank.
3.2 The recorder: record, then move.
The recorder stores each instruction before performing the recorded
move. Its letters are triples (a,h,m): a is the work symbol, h the
history symbol in {E,F} union {records r}, m a mark in {0,1}. A record
r = (q,e,a) consists of a state q, a preceding move e in {-1,0,1}, and a
symbol a. Its states are M_{q,e}, R_r, P_{q,d}, L_{q,d}, one for each
admissible index; d ranges over {-1,0,1}. The rule set is
source read written move target
M_{q,e} (a,h,0) (b_r,h,1) +1 R_r
R_r (c,h,0) (c,h,0) +1 R_r
R_r (c,F,0) (c,r,0) +1 P_{q_r,d_r}
P_{q,d} (c,E,0) (c,F,0) -1 L_{q,d}
L_{q,d} (c,h,0) (c,h,0) -1 L_{q,d}
L_{q,d} (c,h,1) (c,h,0) d M_{q,d}
with the following reading. In the first row q is non-halting, a is the
scanned symbol, r = (q,e,a) is the record of the instruction for that
pair, (q_r,b_r,d_r) is the instruction itself, and h is any history
symbol other than F. There is no first row at a halting state. Rows
two, five, six use h for any history symbol other than F at that
position. Rows four and six require the empty and the record symbols E,
F as displayed.
Lemma 3.1 (the recorder works and is invertible). Start with the work
track equal to the machine tape, empty history everywhere, no marks, and
the frontier at absolute cell c_0 >= 1, meaning the cell c_0 carries F
and every cell to its right carries E. Start in M_{q,0} at the machine
head. Then the recorder simulates the machine without interruption:
after n recorder tours the state is M_{q_n,d_{n-1}}, the work track is
the machine tape after n steps, the head is the machine head, and the
records r_0,...,r_{n-1} occupy cells c_0,...,c_0+n-1 with
J_n = c_0+n > h_n. A tour takes exactly 2(J_n - h_n) + 3 recorder
steps, a finite positive number. The recorder halts exactly when the
machine halts, and with the fresh idle start of (c) it takes at least
one step before any halt.
Second, the six rows define an injective partial map on the whole set of
tapes: each target state can be entered from exactly one source state,
with the written symbol recovering the rest.
Proof. Simulation. The invariant at a tour start: state M_{q,e}, no
marks, records c_0,...,c_0+n-1, frontier F at J_n = c_0+n, head h_n <
J_n, work track correct. The first row applies because h < J and the
cell at the head is not the frontier; it writes the mark 1 at the head
and moves right. Rows two scan right: the head cannot meet F except at
cell J_n, since every other cell to the right of the head carries E or a
record, never F. At J_n row three writes the record r, moves right to
J_n+1; row four requires E there, writes F there, moves left to J_n.
Rows five scan left until the unique mark at h_n, since the mark is the
only one and rows two to four preserve every m = 0 cell they meet.
Row six erases the mark and moves by d = d_r, arriving at h_n + d_r =
h_{n+1} with state M_{q_{n+1},d_r}. The frontier has moved to J_n+1.
Count the steps row by row. Row one is applied once, at h_n. Row two is
applied at h_n+1, h_n+2, ..., J_n-1, which is J_n-h_n-1 times. Row three
is applied once, at J_n, and row four once, at J_n+1. Row five is
applied at J_n, J_n-1, ..., h_n+1, which is J_n-h_n times. Row six is
applied once, at h_n. The total is
1 + (J_n - h_n - 1) + 1 + 1 + (J_n - h_n) + 1 = 2(J_n - h_n) + 3.
This is finite and positive, and every row in it has a defined
successor, so a tour never stops inside itself. With c_0 = 2 and
h_n <= n the count lies between 7 and 4n+7.
Halting. The first row exists only at non-halting states, so the
recorder has no instruction exactly at M_{q,e} with q halt. Every tour
ends at a state M and the next tour begins immediately (or never).
Hence recorder halting at step number k corresponds to machine halting
at step number k.
Inversion. List the four target states. Into M_{q,d} only row six
from L_{q,d} leads, so the source is known and the erased mark is
restored. Into R_r, rows one and two lead: the written mark m = 1
identifies row one (whose source letter was (a,h,0) with a read off from
r) and m = 0 identifies row two, whose source letter is the same as the
written one. Into P_{q,d}, only row three leads, and the written record
letter is r with q_r = q and d_r = d, so the source state R_r and the
source letter (c,F,0) are known. Into L_{q,d}, only row four leads, and
the source letter (c,E,0) is known. Each source is unique, so the map
is injective on its partial domain. []
Remark. The record written at the frontier is not used by the
simulation. It exists to make the inversion work: the control P_{q,d}
alone would not tell us which instruction had been applied, but the
written record does.
3.3 From rectangles to a force: the reciprocal engine.
Now we turn a list of reciprocal rectangle instructions into a force.
The construction is the same for every recorder below, so we state it
once.
Data. A finite list i = 1,...,J of geometric instructions
F_i: P_i -> Q_i, with P_i, Q_i closed rectangles with rational
vertices and positive side lengths in a common rational chart, each
family pairwise separated, F_i the center-to-center map
F_i(y) = q_i + diag(r_i, 1/r_i) (y - p_i), r_i > 0 rational.
Call p_i, q_i the centers. Let s be the largest half-width of any P_i
or Q_i; let T be a closed rational rectangle containing every p_i and
q_i together with the ball of radius 3s about each. Fix the coding
height z_0 and private heights z_1,...,z_J, all rational and pairwise
distinct.
Selectors. Choose smooth periodic planar selectors A_i^-, A_i^+ with
zero mean, equal to one on a closed neighborhood of P_i (respectively
Q_i), vanishing on every other source P_j (respectively every other
target Q_j), j != i, and supported in a collar of their own rectangle.
Nothing is required of A_i^- on a target or of A_i^+ on a source, and
this is exactly what the proof below uses: the particle meets a planar
selector only while it sits in a source or in a target.
Choose height selectors sigma_i, tau_i with zero mean, equal to one on
a closed neighborhood of z_i and zero on a neighborhood of every other
working height. Choose linear profiles g_{i1}(x) = x - p_{i1} and
g_{i2}(y) = y - p_{i2} on intervals containing the closure of every
intermediate coordinate that occurs below. The recipes of Section 2.2
produce all of these, and the profiles are chosen; they are part of the
data.
Lemma 3.2 (reciprocal engine). Under the data and choices above, there
are effective smooth mean-zero transverse fields W_1,...,W_7 on the
torus, supported in the listed stages, such that the solution of the
forced equation with initial velocity zero moves a point (y,z_0), y in
P_i, to (F_i(y), z_0) in time one, and moves every point of a
sufficiently small neighborhood of P_i x {z_0} diffeomorphically onto a
neighborhood of Q_i x {z_0}. Every intermediate point is bounded by
the excursions of Section 2.1. No condition links P_i and Q_j for
i != j.
Proof. The seven fields, in chronological order, are
W_1 = e_z sum_i (z_i - z_0) A_i^-(x,y) lift,
W_2 = e_y sum_i (-r_i) sigma_i(z) g_{i1}(x) shear,
W_3 = e_x sum_i (1/r_i - 1) sigma_i(z) g_{i2}(y) shear,
W_4 = e_y sum_i sigma_i(z) g_{i1}(x) shear,
W_5 = e_x sum_i (r_i - 1) sigma_i(z) g_{i2}(y) shear,
W_6 = sum_i tau_i(z) (q_i - p_i, 0) translate,
W_7 = e_z sum_i (z_0 - z_i) A_i^+(x,y) lower.
Each stage is transverse: stage one and stage seven move only in z with
coefficients independent of z; stages two and four move only in y with
coefficients independent of y; stages three and five move only in x with
coefficients independent of x; stage six has both planar components
independent of x and y. Each field has zero spatial mean because every
term contains a zero-mean selector. Run the stages in disjoint
subintervals of [0,1], with a smooth nonnegative pulse of unit integral
in each, and repeat the seven-stage list with period one.
Follow one point. Suppose its code lies in P_i at height z_0. During
stage one only the i-th term of W_1 is nonzero at the point, because the
other A_j^- are supported away from P_i, so the point rises to height
z_i. During stages two to five only the i-th sigma acts (the private
heights are separated and the point stays at z_i), and the planar
offset (xi, eta) = y - p_i undergoes, in order, the four shears
Y(-r_i), X(1/r_i - 1), Y(1), X(r_i - 1) about p_i. By Lemma 2.1 the
result is diag(r_i, 1/r_i)(y - p_i). Stage six translates the center by
q_i - p_i. Stage seven lowers by z_i - z_0, using A_i^+ which is one
near Q_i while the other A_j^+ vanish there. The final point is
F_i(y) at height z_0. On a small neighborhood of P_i x {z_0} the same
computation applies by continuity, so the time-one map there is the
affine map crossed with the identity in height.
The position is controlled throughout: the planar offset from p_i
during stages two to five is bounded by Lemma 2.2 (or by Lemma 2.3 when
both P_i and Q_i have half-widths at most s and r_i >= 1), and the
profiles were chosen to be linear on an interval containing these
values. The vertical coordinates are z_0, z_i and the interpolating
segments. Every field is a fixed smooth function, so the one-periodic
repetition has bounded derivatives by Lemma 1.1 of Section 1. []
Two remarks used below. First, if all r_i = 1 the four shears are
identity shears and the map is a pure translation; this case is not
excluded and is useful for loading a particle. Second, the engine only
requires the sources to be separated from each other and the targets
from each other; a source may cross or contain another target, and the
proof never looks there.
3.4 The geometric realization, and the proof of Theorem A.
Take the recorder of Lemma 3.1, split every guard of the form "h is not
F" into one rule for each letter h that is not F, and normalize as in
3.1(c) so that the machine takes at least one step. We now instantiate
Lemma 3.2.
Parameters. Let N be the number of recorder states, J the number of
split rules, and m the number of letters; put B = 2m+1 and
ell = 1 / (64 N (1+B)^4).
Every source and target rectangle is a full cylinder inside one mode
square of side ell, so every half-width is at most ell/2. By Lemma 2.2
the excursion of list (a) is at most
(1+B)^4 ell/2 = 1/(128 N).
The input-shifted chart. Let (L_*, R_*) be the rational code of the
initial recorder configuration (left and right of the head). Put the
mode squares, all of side ell, at
initial mode: (1/4 - ell L_*, 1/2 - ell R_*),
other non-halting: (1/4 + 2j ell, 1/2), j >= 1,
halting: (5/8 + 2j ell, 1/2), j >= 1.
Squares are separated: consecutive non-halting origins differ by
ell(2 + L_*) >= ell in the first coordinate, and the halting band starts
at 5/8, far from 1/4 + 2N ell + 1/(128N) <= 1/4 + 1/32 + 1/128.
Inside its square a configuration is coded by (L,R) as in Section 2.
Therefore the code of the initial configuration is exactly
(1/4 - ell L_* + ell L_*, 1/2 - ell R_* + ell R_*) = (1/4, 1/2)
at height z_0 = 1/4, for every input word. This is the trick that makes
the label independent of the input: the chart moves, the label does not.
Heights and selectors. Put z_0 = 1/4 and z_i = 1/2 + i/(8(J+1)).
After the guards are split, every rule reads a window of at most two
cells, so by Lemma 2.4 the same-family gap is at least ell/B^2 in one
coordinate. Choose every planar collar of A_i^pm of width at most
ell/(10 B^2); then a collar meets no other same-family rectangle.
Choose every height collar of sigma_i, tau_i of width at most
1/(32(J+1)), so they are disjoint and none reaches z_0. Use the
translated-copy recipe of Section 2.2 for all of them, so all are zero
mean. Use list (a) of Section 2.1 for the
four shears, and choose the linear profiles to be affine on an interval
of half-width 1/64 (more than the excursion above).
The claim. Fix a non-halting recorder tour whose source code lies in
P_i and whose target code lies in Q_i. Lemma 3.2 with list (a) moves
the particle from the source code to the target code during the seven
stages, and every intermediate position satisfies
x <= 1/4 + 2N ell + 1/(128 N) < 1/2
because the center has first coordinate at most 1/4 + 2N ell, the shear
excursion is at most 1/(128N), and the translation interpolates between
two such centers. The vertical motion does not change x or y.
A transition into a halting code is the only transition whose endpoint
lies in the halting band; there x >= 5/8, and after that no rule has
this code as a source, so nothing moves again.
Proof of Theorem A. Let U be the one-periodic velocity obtained by
running the seven stages of Lemma 3.2 in disjoint subintervals of
[0,1] and repeating with period one, and put f = U_t - nu Laplacian U.
By Lemma 1.1, f is smooth, solenoidal, of zero mean, u = U is the
unique classical solution with zero initial velocity, its flow is
volume preserving, and all mixed derivatives of u and f are bounded;
the energy is bounded because there are finitely many phase templates.
Splitting the translation stage into its x and y parts makes every
stage move in exactly one coordinate direction.
For the particle, use induction on the tour number. At time 0 it sits
at the label, which is the code of the initial configuration. Suppose
at integer time n it sits at the code of the recorder configuration
after n tours. During the next unit of time it follows exactly the
seven stages of the branch whose source is that code, since every other
branch's planar selectors vanish there, and arrives at the code of the
next configuration at time n+1. If the recorder is in a non-halting
mode, this branch exists, its source and target codes have x < 1/2, and
by the claim the whole path has x < 1/2, so the particle misses the
event. If the recorder is in a halting mode, the code has x >= 5/8 and
the particle enters the event at the last stage of that transition and
stays there. By Lemma 3.1 the recorder halts exactly when the machine
halts. This proves Theorem A (i), (ii) and (iii) for the strip
1/2 < x < 7/8 and the label (1/4,1/2,1/4).
Effectiveness. Every parameter above is a rational number written down
from the finite machine table and the finite input, and every profile is
an explicit smooth function of the coordinate with a computable bound on
each derivative, so every requested derivative of f is computable at
every rational space-time point. []
Remark (a second chart with a cheaper excursion bound). Because both
the source and the target half-widths are at most ell/2, Lemma 2.3
bounds the same excursion by 3 ell/2 instead of (1+B)^4 ell/2. Taking
ell = 1/(64(N+1))
and the same origins and heights, the excursion is at most 3ell/2, so
non-halting paths have x <= 1/4 + 2N ell + 3ell/2 < 1/2 and halting
codes have x in [5/8, 5/8 + 2N ell] inside (1/2, 3/4). The event may
then be narrowed to 1/2 < x < 3/4. This version does not need the base
B to be small, which matters in Section 4 where the alphabet is larger.
It uses the same six rows and the same inverse proof; only the chart
changes.
4. OTHER RECORDERS, LOADERS, AND CHARTS
The proof of Theorem A is complete. This section collects variants. The
first is used in Section 5; the fourth explains how to make a onetime
loader and how to change the physical scale; the rest show that the
recorder of Section 3 is not fragile.
4.1 A recorder that keeps the head marked (used in Section 5).
Here the unique mark sits at the machine head at every checkpoint and is
moved along with it. Letters are (a,m,g) with g in {E,F} union {i}; the
controls are C_q, D_i, R_i, L_q, and there is a fresh idle start q_b
with no incoming rule and no L_{q_b}:
1. non-halting C_q: require m_0 = 1 and, if d_i != 0, m_{d_i} = 0.
Write b_i, move the mark to index d_i, shift by d_i, enter D_i.
2. D_i: require m_0 = 1, shift right, enter R_i.
3. R_i: require m_0 = 0. If g_0 != F, scan right in R_i. If g_0 = F
and g_1 = E, write i at 0 and F at 1, shift left, enter L_{q_i}.
4. L_q: if m_0 = 0 and g_1 != F, scan left in L_q. If m_0 = 1, enter
C_q without editing or moving.
Lemma 4.1 (the marked recorder works and is invertible). Start with the
machine tape on the work track, one mark at the machine head, empty
history everywhere, and the frontier at J_0 = c_0 >= 2. Then the
recorder simulates the machine; after the n-th tour the mark is at the
machine head h_n, the records occupy c_0,...,c_0+n-1, and the frontier
F is at J_n = c_0+n > h_n. One tour takes 2(J_n - h_n) + 2 recorder
steps, where h_n is the new machine head after the tour's work move.
Every target state has a unique source, so the partial map is injective.
Proof. Simulation. Row 1 is the work move: the written symbol replaces
the scanned one, the mark is written at the new head cell d_i before the
shift, and after the shift by d_i that cell is index 0, so the mark is
still at the head. Row 2 steps off the marked cell to its right, and
its guard m_0 = 0 says the mark is behind. Row 3 scans right; the first
F is the frontier because fresh cells carry E and only the frontier
carries F, so the scan stops at J_n, where the record i and the new
frontier F are written over F and E and the head steps back to J_n - 1.
Row 4 scans left; its guard g_1 != F prevents mistaking the new frontier
at J_n for the marked head. At h_n the mark is found, and the tour
ends in C_{q_i} without moving. Count: row 2 is one step, the right
scan is J_n - h_n - 1 steps, row 3 is one step, the left scan from
J_n - 1 to h_n + 1 is J_n - h_n - 2 steps, and row 4 at h_n is one step;
total 2(J_n - h_n) + 2. This is finite and positive. A halting state has
no row 1, so halting stops the recording exactly as before.
Inversion. Into C_q only row 4 from L_q leads: the marked tape is left
unchanged and is restored. Into D_i only row 1 leads, and i names the
instruction, hence its scanned symbol, its written symbol and its
displacement; the source letter is restored and the source position is
the target position minus d_i. Into R_i only row 2 from D_i leads.
Into L_{q_i} only row 3 leads, and the written pair (i,F) identifies the
rule and restores the overwritten (F,E). Uniqueness of the source in
each case is what we needed. []
4.2 Other recorders, in one paragraph each (not used below).
Write-first. One can move and write first and record afterwards; the
rows change, the inverse test is still of the form "the target control
determines the discarded symbol and the position". Neighbour guards.
One can append the history two cells at a time, saving local steps, at
the price of a guard on a neighbouring cell, which the inverse test then
has to verify. Tagged initializer. One can write a finite input from
an entirely blank tape inside the repeated table, so that the loading
also happens periodically from time zero; the initialization gets its
own tag so that its arrivals are disjoint from ordinary ones. Origin
flag. One can carry a bit marking the original cell zero to recover
absolute indexing without reading the history. Remote centre. All
branches can be routed through one common centre before being delivered,
which gives a small chart. Each of these is a finite table plus the
same two checks: an invariant during the simulation, and a case list for
the inverse. None of them changes the analytic part.
4.3 A separate loader.
Here is a way to keep the repeated processor independent of the input.
Use a horizontal transverse field whose coefficient depends only on
height:
V(x,y,z) = (A, 0, 0) chi(z - z_0)
with chi a smooth profile equal to one near the coding height z_0 and of
zero mean in z. The particle at height z_0 is translated by A during the
loading interval; a particle away from that height is not. Choosing A
equal to the displacement from a fixed starting label to the rational
initial code, and running the loader once during [0,1], sends the
particle to the initial code; afterwards the processor of Section 3 runs
once per unit of time, so the event is reached exactly when the machine
halts, after a delay of at most one. The force remains smooth,
solenoidal, and of zero mean, and the velocity is zero near every
integer time by the pulse convention. This gives periodicity after
loading, not from time zero; Section 3.4 gives from time zero.
4.4 Loading from the centre, in eight phases.
For a chart with everything near the centre, one can also proceed as
follows. Refine each single-cell rule by the letter on its left, so
that every source rectangle has side lengths lambda/D in both
directions (D the base, lambda the chart scale). Then a branch has a
planar map F_i = q_i + diag(mu_i, 1/mu_i)(y - p_i) with all p_i, q_i in
[1/4, 3/4]^2. Use eight stages: lift by j_i/B_0 at height j_i/B_0;
translate the centre to the common centre c_* = (1/2,1/2); perform
X(1), Y(1/mu_i - 1), X(-mu_i), Y(-(1/mu_i - 1)/mu_i); translate to the
target centre; lower. The four central shears carry the offset (xi,
eta) to
(xi+eta, eta),
(xi+eta, (1/mu_i - 1) xi + eta/mu_i),
(mu_i xi, (1/mu_i - 1) xi + eta/mu_i),
(mu_i xi, eta/mu_i).
A short check: since mu_i and 1/mu_i are at most D, all four
intermediate points stay within the chart, the profiles remain linear,
and the endpoint is the prescribed target. Loading from (1/2,1/2,0)
to the rational initial code uses one horizontal pulse with a zero-mean
height selector; in a non-halting run every path stays in x < 9/16,
while halting codes lie in [5/8, 3/4]. The event is 9/16 < x < 3/4.
With the cube-root clock g(t) = (1+t)^{1/3} - 1 the codes occur at
times (2+j)^3 - 1 and Proposition 1.3 gives, for all k and alpha,
|| d_t^k D^alpha u || + || d_t^k D^alpha f ||
= O_{k,alpha} ((1+t)^{-2/3}).
The eight stages each move in one coordinate direction, so the velocity
uses one Cartesian component at a time.
4.5 A side-ten chart and a change of scale.
Sometimes it is convenient to work on T_10^3, where there is room for
large rational coordinates. Take the recorder of 4.1 with one halt
label, add a copied origin bit at absolute cell zero, keep the frontier
at two, and code in base K = 2|Gamma|+1 with odd digits, where Gamma is
the augmented alphabet. Put
r = 1/(4m), non-halt origins (2 + 2rj, 2), halt origin (6,2),
coding height 2,
so that non-halting codes have x < 5 and halting codes have 6 <= x <=
6+r. Use collars r/(4K^2), shears from list (a) about the branch
centres, and private heights 4 + i/(J+1). The excursion of list (a) is
at most r (Lemma 2.2 with B = K), and the profiles stay linear because
the source half-widths are at most r/2. The event is 5 < x < 8.
A construction on T_10^3 with viscosity nu_10 and side-ten data turns
into one on T^3 by the change of variables, for T > 0,
v(s,y) = (T/10) U(Ts, 10y), p(s,y) = (T^2/100) P(Ts,10y),
f(s,y) = (T^2/10) F(Ts,10y), nu_1 = 100 nu_10 / T.
Check it term by term: v_s = (T^2/10) U_t, (v.grad)v =
(T^2/10)(U.grad)U, grad_y p = (T^2/10) grad_x P, and Laplacian_y v =
10T Laplacian_x U, so every term of the side-ten equation is multiplied
by T^2/10 and the viscosity becomes nu_10 10T (10/T^2) = 100 nu_10/T.
Thus with T = 1 a point at x becomes the point at x/10 on the unit
torus, the side-ten label (2,2,2) becomes (1/5,1/5,1/5), and the event
5 < x < 8 becomes 1/2 < y < 4/5; to keep a prescribed unit-torus
viscosity nu one starts with nu_10 = 100 nu. Keeping the side-ten
viscosity itself instead forces T = 100, which changes the time period.
5. WHOLE BOXES OF POSITIVE THICKNESS
5.1 Parking, then delivering.
The rectangle maps of Section 3 are stated on sheets. Here the same
reciprocal maps are performed on boxes P_i x [-1/2,1/2] of thickness one.
The only new difficulty is conflict: while one box moves, the others must
stay exactly where they are, and targets may overlap sources. The cure
is to empty a warehouse first: move every source into its own parking
square, and only then deliver them one at a time to their targets.
Lemma 5.1 (parking before delivery). Let P_i, Q_i, 1 <= i <= l, be
closed rational rectangles with positive side lengths at most one,
pairwise separated within each family, and let F_i(x) = q_i +
diag(a_i, 1/a_i)(x - p_i) with rational a_i > 0 map P_i onto Q_i. Let
J_0 = [-1/2,1/2]. Then there are smooth fields, one at a time in
disjoint slots inside [1/4,3/4], each transverse and each compactly
supported in the coordinates it depends on, whose composition realizes
all the maps on the boxes P_i x J_0. If a source and its target both lie
in x < 0, the whole moving box stays in x < 0.
Proof. If l = 0 take the zero field. Otherwise let x_min be the least
first coordinate of any point of any P_i or Q_i, and put
g_i = (min(0,x_min) - 5 - 3i, 0), G_i = g_i + J_0 x J_0.
The parking squares G_i are separated from each other (their centres are
three apart and they have side one) and from every source and target
(their first coordinates are at most min(0,x_min) - 5 + 1/2, while all
sources and targets lie at first coordinate at least min(0,x_min)).
Let d_0 be the minimum of one and all the positive separations among
sources, targets, and parking squares, and use collars d_0/4. All
cutoffs below are one on a neighborhood of their own square or slab and
vanish outside these collars.
Schedule ten slots per box: three to evacuate (lift by Z = 4, translate
the centre to g_i at height 4 + J_0, lower by 4) and seven to deliver
(the same lift, four shears about g_i, translate to the target centre,
the same lower). Put each slot in a disjoint subinterval of [1/4,3/4]
and run one pulse of unit mass in each.
The fields. A vertical motion over a footprint C is
+- Z chi_C(x,y) e_z,
a horizontal translation by (b_1,b_2) at the lifted height is
(b_1, b_2, 0) chi_{J_Z}(z), J_Z = 4 + J_0,
and a shear about g_i which adds a_i (y - g_{i2}) to x is
a_i (y - g_{i2}) chi_{[g_{i2}-2,g_{i2}+2]}(y) chi_{J_Z}(z) e_x,
with the analogous field for the other direction. Each is transverse:
the first depends only on x,y, the second only on z, the third (in x)
on y,z.
Geometry of one moving box. During its own slot the box in question sits
on the plateau of the active profile, so its points move identically and
the ODE solution is the intended lift, translation, or shear. Write the
initial offset from the centre as (xi, eta). Since the source and target
half-widths are at most 1/2, we have |xi|, |eta|, |a_i xi|, |eta/a_i| <=
1/2. The four endpoints of list (a) about g_i are
(xi, eta - a_i xi),
(a_i xi + (1/a_i - 1) eta, eta - a_i xi),
(a_i xi + (1/a_i - 1) eta, eta/a_i),
(a_i xi, eta/a_i),
and each has both coordinates of modulus at most 1: the second coordinate
is |eta| + |a_i xi| <= 1 in the first two, and the first coordinate is
|a_i xi| + |eta| <= 1 because |1/a_i - 1| <= 1 when a_i >= 1 (otherwise
swap the two coordinates). Partial pulses interpolate between these
points, so every point of the box stays within distance 1 of its centre
throughout the shears, and the displayed cutoffs equal one there.
Other boxes. While box i moves, every other box is either an unmoved
source, a parked box, or a completed target. Their footprints are
separated, so every vertical profile vanishes on them; and their heights
are the plane J_0 (all other boxes are in their slots or at rest), while
the shear and translation profiles are supported near J_Z. Hence the
other boxes do not move during slot i. Uniqueness of solutions of the
common ODE then identifies the composed motion with the prescribed maps.
Sign. A parking centre has g_{i1} <= min(0,x_min) - 5 <= -5, all
vertices of the source and target have nonpositive first coordinate when
both lie in x < 0, translations interpolate between two nonpositive
first coordinates, vertical motion does not change x, and the shears add
at most 1 to |x - g_{i1}|. So x <= -5 + 1 + 1/2 < 0 throughout. []
Theorem C is Lemma 5.1 together with the following standard conversion.
Choose R_* larger than every coordinate of every tracked path and every
support; for the application below, R_* = 100 + 2N + 4 max(1,l) is
enough, because the rectangles lie in [-2N-1,3] x [-1,2], parking adds
at most 5 + 3 max(1,l) to the negative first extent, shears add at most
two, collars at most 1/4, and heights stay below 4 + 1/2 + 1/4. Scale
by lambda = (8R_*)^{-1} into the unit torus, and for every pulse whose
transverse coordinate set is I, with j = min I, replace its scaled field
F by
F(x) - F(x + e_j/2).
The support of F lies in |x_i| < 1/8 for i in I, so the translated term
vanishes on every tracked path; the difference has zero mean because the
torus integral is translation invariant. Divergence and self-advection
are preserved by scaling and by translation of the space variable, and
every pulse is still transverse.
5.2 A whole-box version with a half-circle observer.
Apply Lemma 5.1 to the marked recorder of 4.1 to obtain a positive
thickness version of Theorem A. Place the unit mode squares at
(alpha_s, 0), with alpha = 1 for the halting mode and alpha = -2j,
j >= 1, for the others; thicken every branch by J_0. Non-halting boxes
lie wholly in x < 0 and halting codes lie in 1 < x < 2. Apply the lemma
to the list of stepping branches and separately to the single loading
translation from the cube J_0^3 to the cube centred at the rational
initial code. Concatenate the loading interval and the repeated
stepping interval, and prescribe f = U_t - nu Laplacian U.
By Lemma 1.1 the force is smooth, mean zero and solenoidal, the solution
is unique in the classical class with pressure zero, and the flow is
volume preserving. In the scaled chart the fixed label is the torus
origin and the event is the positive half circle 0 < x < 1/2. At time
1+j the particle is at the scaled code lambda kappa(T^j c_0), where kappa
is the coding and T the recorder transition. A halting computation puts
it in 1 < x < 2 before scaling, hence in (0,1/8) after scaling and
reduction, which lies in the event. A non-halting computation never
leaves x < 0 before scaling, hence never enters (0,1/2) after reduction:
the sign part of Lemma 5.1 covers the stepping slots, and during loading
the origin of the loading cube starts at x = 0, moves to a negative
parking centre, is carried by shears, and ends at the negative initial
code, so its first coordinate stays nonpositive. No scaled path leaves
the cube of half-width 1/8, so reduction modulo one adds no crossings.
With the unslowed clock the force is periodic after loading and its
repeating part depends only on the machine table. With the logarithmic
clock of Lemma 1.2 every mixed derivative of the force is bounded and
square integrable in space and time, and code j is reached at
t = exp(1+j) - 1. Both statements describe the same finite pulse list,
whose construction never runs the simulated machine.
6. CHANGING PLANAR AREA: PROOF OF THEOREM B
6.1 The three-phase sheet-scaling triple.
Reciprocal scaling diag(r,1/r) preserves planar area. A general prefix
rule that inserts a history symbol changes the area of its rectangle, and
volume preservation then forces the normal direction to move as well.
Here is the elementary device that does it. Work on T_10^3, near the
processing centre v_* = (5,6) and the processing height 5.
Let chi be an even smooth cutoff with chi = 1 on [-1/4,1/4] and support
in [-1/2,1/2], and put, with period 10 in each variable,
C_{h,c}(s) = sum_k chi((s - c - 10k)/h),
D_{h,c}(s) = sum_k (s - c - 10k) chi((s - c - 10k)/h).
Then C is a periodic cutoff equal to one near c and D is odd about c,
so D has zero mean and equals s - c near c. For a coordinate j in
{1,2} put
H_j = D_{1/4,5}(x_j) C_{1/4,6}(x_{3-j}), B = D_{1/4,5}(z).
All three have zero mean, are smooth, and equal their linear parts on
the cube |x_j - 5| <= 1/8, |x_{3-j} - 6| <= 1/8, |z - 5| <= 1/8.
Lemma 6.1 (sheet triple). Run, in disjoint slots,
W^1 = e_z H_j, W^2 = e_j (lambda - 1) B, W^3 = -e_z H_j / lambda,
with lambda > 0 rational. Each field is transverse and of zero mean.
A point at (5 + r, 6, 5 + zeta) with |r|,|zeta| <= 1/8 goes to
(5 + lambda r + (lambda - 1) zeta, 6, 5 + zeta/lambda)
and in particular a point with zeta = 0 goes to (5 + lambda r, 6, 5).
The two relevant coordinates transform by the matrix
[[lambda, lambda - 1], [0, 1/lambda]],
whose determinant is one: the sheet is scaled by lambda while a nearby
normal offset is divided by lambda.
Proof. Phase one changes z by H_j, which equals r on the plateau:
z becomes 5 + zeta + r. Phase two changes x_j by (lambda-1)B(z) with
B = z - 5 = zeta + r: x_j becomes 5 + r + (lambda - 1)(zeta + r) =
5 + lambda r + (lambda - 1) zeta. Phase three changes z by
-H_j/lambda with H_j now equal to x_j - 5 = lambda r + (lambda-1) zeta,
so z becomes 5 + zeta + r - r - (lambda-1) zeta/lambda = 5 + zeta/lambda.
All points stay on the plateaus because every intermediate coordinate
is within 1/8 of the centre: |r|, |zeta| <= 1/8 and lambda, 1/lambda
are bounded on the finitely many uses below. The matrix displayed has
determinant lambda * (1/lambda) = 1. []
6.2 Sequential realization of arbitrary diagonal maps.
Data as in Theorem B: closed rational rectangles P_i, Q_i inside
[2,3]^2 with positive side lengths, each family pairwise separated, and
F_i: P_i -> Q_i the centre-to-centre map with linear part
diag(lambda_{i1}, lambda_{i2}), both entries positive rational. Write
v_i, v_i' for the centres and h_i, h_i' for the half-width vectors; all
coordinates lie in [2,3], so all half-widths are at most 1/2. Let
d > 0 be one tenth of the minimum of one and of all within-source and
within-target separations.
Step 1: evacuate. For each i in turn, lift the sheet from height 2 to
height 5, shift it by (4,0), and lower it to height 2. Step 2: deliver.
After every source has been evacuated, process the sheets in order: lift
from 2 to 5, translate the centre to v_*, run the triple in coordinate 1
with lambda = lambda_{i1}, run the triple in coordinate 2 with
lambda = lambda_{i2}, translate the centre to v_i', lower to height 2.
The triple contracts when lambda < 1 and expands when lambda > 1, so one
device does both jobs. Each triple is three pulses, so a delivery is
1 + 1 + 3 + 3 + 1 + 1 = 10 pulses and the whole schedule uses
3N + 10N = 13N pulses inside [1/4,3/4].
Why it is legitimate. The evacuation exists precisely because a target
may lie on a source: while sheet i is delivered, all other sheets are
either stored (at height 2 with second coordinate in [2,3]) or already
delivered (at height 2 with second coordinate in [2,3]), and the
footprint of sheet i at height 5 is the complement of the plane, so no
conflict occurs. Vertical pulses are supported over one footprint,
horizontal translations near heights 5 and 8, and the triple's profiles
near height 5 and second coordinate 6. Every resting sheet is off all
these supports. All supports and all moving paths lie inside the
side-ten chart, so the periodic copies create no intersection.
Theorem B follows. Repeat the displayed finite pulse list with period
one from time zero, let U be the resulting velocity, and put
f = U_t - nu Laplacian U. Every pulse is transverse and of zero mean,
the pulses have disjoint time supports and zero collars at the integers,
every parameter is rational and every profile explicit, so Lemma 1.1
gives a smooth mean-zero solenoidal force, pressure zero, a unique
classical solution with zero self-advection, bounded mixed derivatives,
bounded kinetic energy, and velocity zero near integers. At time one
each P_i x {2} is carried to (F_i(P_i), 2) = (Q_i, 2) with the prescribed
linear part, which is what the theorem asserts. The normal action of
each triple is the determinant-one matrix of Lemma 6.1, so a thin
neighbourhood of a sheet is carried to a thin neighbourhood of the target
sheet; nothing is asserted for a box of positive thickness, where the
normal offsets would accumulate.
The observation bound. A useful extra fact, which will drive the
observer below. Whenever a point's height lies in (3/2, 5/2), its first
coordinate is one of
x^-, x^- + 4, x^+
where x^-, x^+ are the first coordinates of its source centre and of its
target centre. Reason: at such heights the point is being lifted,
lowered, or waiting, all of which happen over a source, a storage point
or a target; horizontal translation happens only at height 5 and the
triple only at heights 5 +- 1/2. This is the height guard.
6.3 A stack recorder, and its observer.
The storage construction of 6.2 acts on any list of separated rectangles.
To get a machine on a sheet we must produce such a list from a machine,
and then find a fixed strip that a non-halting particle never enters.
Here is one recorder, arranged so that both coordinates of a code are
read off from the two stacks. Normalize to one halt label and let A be
the tape alphabet with blank b_0. The stack alphabet is
A union {bottom, diamond} union {eta_i}
and the controls are R_q, T_i, S_p. A left stack has the form
L = ell bottom H, where ell in A* lists the working cells left of the
head, nearest first, bottom separates them from the retained history H,
and the right stack begins with the scanned cell. Diamond marks the
beginning of the updated right word while T_i transfers the finite left
word above it, and S_p restores that word until diamond is exposed and
removed. A fresh symbol eta_i below bottom records the instruction case.
Give each case of an instruction (q,a) -> (p,b,d) its own index i, with
p(i) = p, and use the primary rules
d = 0: (R_q; empty, a) -> (T_i; empty, diamond b)
d = +1: (R_q; empty, a) -> (T_i; b, diamond)
d = -1, c in A: (R_q; c, a) -> (T_i; empty, diamond c b)
d = -1, empty left: (R_q; bottom, a) -> (T_i; bottom, diamond b_0 b)
and the transfer and restore rules
(T_i; c, empty) -> (T_i; empty, c)
(T_i; bottom, empty) -> (S_{p(i)}; bottom eta_i, empty)
(S_p; empty, c) -> (S_p; c, empty)
(S_p; empty, diamond) -> (R_p; empty, empty)
for every c in A.
Lemma 6.2 (the separator recorder works and is invertible). Start in
(R_{q_0}; bottom b_0^..., w b_0^...). At a ready state with
L = ell bottom H the primary rule yields (T_i; ell', bottom H; diamond Y')
with the correctly updated tape; the transfer moves ell' rightwards,
inserts eta_i below bottom, and the restore returns precisely those work
symbols until diamond is exposed and removed. The new ready
configuration is (R_{p(i)}; ell' bottom eta_i H; Y'), reached after
2|ell'| + 3 rules, a finite positive number even when ell' is empty.
Halting of the recorder and halting of the machine agree. The map is
injective on its partial domain: sources are separated by control and
tested top symbol; into T_i the primary arrival has diamond on top of
the right stack while loop arrivals have a real symbol there; into S_p a
transfer arrival has bottom eta_i on the left while a loop has a real
letter; into R_p there is exactly one incoming rule.
Proof. Immediate from the description, with one case to note: for a
left move with an empty left word, the missing cell is the implicit
blank b_0, which the last primary rule supplies. The count is one
primary step, |ell'| transfer steps, one bottom step, |ell'| restore
steps and one final removal. []
Coding and observer. Use a common digit dictionary, and let m be the
number of entries other than the halt control. Put K = 8(m+1), give the
m entries the digits 2,4,...,2m, and give the halt control the digit
3K/4. For a finite word v put e(v) = sum_j d(v_j) K^{-j} and
I(v) = [e(v), e(v) + K^{-|v|}], and code
(s,L,Y) |-> ( 2 + e(sL), 2 + e(Y), 2 ) in T_10^3.
A rule (s; alpha, beta) -> (s'; alpha', beta') has rectangles
P_i = (2 + I(s alpha)) x (2 + I(beta)),
Q_i = (2 + I(s' alpha')) x (2 + I(beta')),
both inside [2,3]^2 and both families separated. The affine factors are
K^{|alpha|-|alpha'|} and K^{|beta|-|beta'|}; the control digit cancels in
the first ratio because it has length one at both ends. Non-halting
first coordinates are at most 2 + (2m+1)/K < 9/4, and halting codes lie
between 11/4 and 3. The initial code is rational.
These rectangles satisfy every hypothesis of 6.2, so load (2,2,2)
horizontally to the rational initial code during [0,1] and repeat the
schedule. The event is
5/2 < x < 7/2 and 3/2 < z < 5/2.
A halting code lies in it, including an initially halted input after
loading. A non-halting run has x < 9/4 at every endpoint, and every low
height point has first coordinate in {x^-, x^- + 4, x^+} by the height
guard: either below 9/4 or at least six, both outside the event; at
other heights the height condition excludes the point. So no
intermediate position enters the event, although an upper horizontal
route crosses the observer's projection. Direct forcing has zero
pressure and is periodic after loading; the logarithmic clock of
Lemma 1.2 instead gives ||f||_infty = O((1+t)^{-1}) and square
integrable forcing with the same event.
6.4 Fifteen simultaneous phases for strip data.
The sequential construction needs 13N slots. When the rectangles all
lie in a narrow horizontal strip, one can process all branches at once,
at private heights, using fifteen stages.
Data. Rectangles D_i = p_i + [-s_{i1},s_{i1}] x [-s_{i2},s_{i2}] and
T_i = q_i + [-t_{i1},t_{i1}] x [-t_{i2},t_{i2}], each family separated,
all inside the strip 1/4 - 1/32 < y < 1/4 + lambda + 1/32 on the unit
torus, with every half-width smaller than 1/2. For N > 0 put
z_0 = 1/2, z_i = 1/4 + i/(2(N+1)), kappa = 1/(16(N+1)),
epsilon = (1/2) min over i,j of {s_{ij}, t_{ij} }.
Choose a symmetric cutoff chi_i about each rectangle, with collars
smaller than 1/32, and a height cutoff zeta_i about z_i, and set
G_i(z) = (z - z_i) zeta_i(z), which has zero mean together with its
derivative. Translate a copy by omega = (0,1/2), which misses every
tracked rectangle, and take differences to get zero means: the lift of
D_i uses chi_i^D(y) - chi_i^D(y - omega), and similarly for the lower.
The strip triple. For centres o_i, cutoffs chi_i and factors mu_i > 0
put
X^1 = e_z sum_i kappa (y_j - o_{ij}) chi_i(y),
X^2 = e_j sum_i ((mu_i - 1)/kappa) G_i(z),
X^3 = -e_z sum_i (kappa/mu_i)(y_j - o_{ij}) chi_i(y).
At height z_i with offset xi in coordinate j, phase one lifts by
kappa xi, phase two multiplies the offset by 1 + (mu_i - 1) = mu_i, and
phase three lowers by (kappa/mu_i)(mu_i xi) = kappa xi, returning to
z_i. Each field is a transverse shear; each has zero mean because its
planar factor is odd about the rectangle centre, or its height factor is
odd about z_i and multiplied by a cutoff.
The schedule. Lift D_i from z_0 to z_i (1 stage). Contract coordinate
one by mu_i = epsilon/s_{i1} (3 stages), contract coordinate two by
mu_i = epsilon/s_{i2} (3 stages), so D_i becomes the tiny square
p_i + [-epsilon,epsilon]^2. Translate by (q_i - p_i) G_i'(z) (1 stage).
Expand coordinate one by t_{i1}/epsilon (3 stages), two by
t_{i2}/epsilon (3 stages). Lower to z_0 (1 stage). Total
1 + 6 + 1 + 6 + 1 = 15 stages, each in its own slot inside [1/4,3/4].
Why it works. During contraction the whole projection stays inside the
source rectangle; during expansion it stays inside the target rectangle;
so every cutoff used remains on its plateau, including after the other
coordinate has moved. The middle translation is exactly by q_i - p_i at
height z_i. Therefore the period map is
(y, z_0) |-> ( q_i + diag(t_{i1}/s_{i1}, t_{i2}/s_{i2})(y - p_i), z_0 )
for y in D_i, with the two coordinates handled independently. A small
normal offset zeta is carried, during one triple, by
(xi, zeta) |-> (mu_i xi + ((mu_i - 1)/kappa) zeta, zeta/mu_i),
whose determinant is one; the restriction to zeta = 0 multiplies the
horizontal offset by mu_i. So a sheet may change area, and the normal
direction pays for it.
Where strip data come from. A prefix-rule recorder that replaces two
finite stack prefixes and retains the tails produces rectangles whose
ordinates are all codes of right prefixes, hence all lie in one narrow
interval; both families are then in a strip. Such a recorder writes one
fresh tag at each machine step and never removes a recorded tag, so
after j steps the finite control holds at most j tags to transfer and the
next machine step takes at most j + 3 recorder rules; if n_k is the rule
count after k machine steps then k <= n_k <= k(k+1)/2 + 2k. None of the
intermediate controls is terminal, so the recorder halts exactly when
the machine does. Disjointness of the two rectangle families follows as
in Lemma 2.5, from the control and the tested top symbols: primary
arrivals at a transfer control carry a tag on top, loop arrivals carry a
real letter, and exits into the main controls have distinct real top
symbols or distinct two-symbol prefixes.
The observer. With the strip chart of this section, non-halting source
and target rectangles have first coordinates in (1/8,1/4), and
contraction, translation and expansion keep the point in that band;
loading follows a segment from (1/2,1/2,1/2) into it. Halting codes lie
in (11/16,13/16). Hence the fixed event 5/8 < x < 7/8 is entered exactly
on halting, at all real times, including for an initially halted input
after loading. The finite positive rule counts show that no machine
step is left unfinished; direct transverse forcing gives the smooth
mean-zero solenoidal force, pressure zero, and periodicity after loading.
The repeated processor depends only on the transition table, and the
input affects only the rational loading code.
7. THE SAME EQUATION IN MATERIAL LABELS
Let u, p be any smooth torus solution built above and let X(t,a) be its
material flow: X_t(t,a) = u(t,X(t,a)), X(0,a) = a. Write
M(t,a) = D_a X(t,a) and P(t,a) = p(t,X(t,a)).
Differentiating the flow equation gives
dM/dt = (D_x u)(t,X) M, M(0) = I,
and the Jacobi formula gives d(det M)/dt = div_x u (t,X) det M = 0, so
det M = 1 for all time: the flow is volume preserving. In particular
the observed particle is carried by the unique solution's own flow, not
by some auxiliary map.
The equation for X in material labels, component by component, is
d^2 X_i / dt^2 = -(M^{-T} grad_a P)_i
+ nu div_a ( M^{-1} M^{-T} grad_a (dX_i/dt) )
+ f_i(t, X(t,a)), det M = 1.
Indeed, differentiating X_t = u(t,X) in t gives the Eulerian material
derivative u_t + (u.grad)u at X, which the equation at X identifies with
-grad_x p + nu Laplacian_x u + f. The chain rule gives
(grad_x p)(t,X) = M^{-T} grad_a P(t,a).
For the diffusion term, first note that
(grad_x u_i)(t,X) = M^{-T} grad_a (dX_i/dt),
because dX_i/dt = u_i(t,X). Then, for a smooth periodic test function
phi, using det M = 1 to change variables,
integral (Laplacian_x u_i)(t,X) phi(a) da
= -integral (grad_x u_i)(t,X) . M^{-T} grad_a phi(a) da
= -integral M^{-1} M^{-T} grad_a(dX_i/dt) . grad_a phi da,
and periodic integration by parts gives the divergence form displayed.
Smoothness upgrades the test-function identity to a pointwise one.
All the shear constructions have p = 0 and hence P = 0. Since the
velocity they produce is a classical solution with zero initial velocity,
the observed particle's path is exactly the material evolution governed
by this equation, with the pressure term absent. Nothing in the
argument used a discretization or a finite-precision code: the codes are
exact rational numbers and the membership question is asked about exact
real times.
8. RELATION TO EARLIER WORK, AND WHAT IS DIFFERENT HERE
Positional coding. Moore's generalized shifts turn a symbol sequence into
a point of a square by base-B codes and admit smooth realizations for
invertible shifts (Moore 1990, 1991). We use the coding as an interface:
the closed rectangles of Lemma 2.4 and the exact linear map of Lemma 2.5
are the only objects a rule produces, and all geometry after that is
shears.
Reversibility. Bennett's simulation records each instruction and checks
disjoint domains and disjoint ranges (Bennett 1973); Lecerf built
reversible machines earlier (Lecerf 1963); Landauer explains why the
record cannot be thrown away (Landauer 1961). Our recorders follow that
discipline: each rule set is inverted case by case on its whole partial
domain, not only on initialized tapes, and the counting arguments show
that one machine step is a finite positive number of recorder steps.
Fluid computation. Cardona, Miranda, Peralta-Salas and Presas realise
computation by stationary Euler flows on a three-sphere with a Riemannian
metric adapted to the construction (CMPP 2021); their Proposition 5.1
contracts, transports and expands neighbourhoods, the same organization
as the sheet triple of Section 6. Cardona, Miranda and Peralta-Salas
construct Turing complete Beltrami fields on R^3; there the simulation
lives on a noncompact set and the fields have infinite energy (CMP 2023).
Dyhr, Gonzalez-Prieto, Miranda and Peralta-Salas obtain steady viscous
computation after deforming the metric and using the Hodge Laplacian on
one-forms (DGMP 2026).
What is done here. On the standard flat torus, with the usual flat
Laplacian, a fixed positive viscosity, and zero initial velocity, an
external force read off from a finite machine table and a finite input
makes one fixed particle enter one fixed open strip exactly when that
machine halts, at all real times, with pressure zero and all mixed
derivatives bounded. The forcing is effective and its profiles are
elementary. The same shears realize arbitrary positive diagonal maps on
sheets, with explicit normal compensation, and reciprocal maps on whole
boxes of positive thickness with an all-time sign guard. The uniqueness
step is the classical energy comparison of Leray's method (Leray 1934):
it compares the displayed solution with any classical solution of the
same force, and says nothing about existence for arbitrary data.
Composing Theorem A with a decision procedure for the particle event
would decide halting, including Turing's symbol-printing version
(Turing 1936). With the interpreter of the appendix the machine may even
be fixed and only the input varied.
APPENDIX: ONE FIXED INTERPRETER
The compiler of Section 3 takes a finite machine table together with an
input. It is sometimes preferable to fix one machine and vary only its
input. This appendix constructs such a machine, in the same tape model,
in enough detail that its existence is not in doubt.
Step 0: normalization. Delete all outgoing rows of designated halt
states, and complete every missing state-symbol pair at a non-halting
state by an unchanged-symbol, no-move row into one fresh halt state with
no outgoing rows. Then "no row matches" is the same as "halted", which
is what an interpreter can test.
Step 1: serialization. Give interpreted states and symbols positive
integer indices, with the blank having index one. Write an index m as a
block of m ones followed by a separator. Use distinct syntax symbols
for begin, row-end, table-start, table-end, and the three head motions.
Serialize a machine and input as its initial state, its input fields in
reverse word order, and its finite list of rows, each row containing
current state, scanned symbol, next state, written symbol, and motion.
Correctness is claimed only on these valid finite descriptions.
Step 2: a five-tape interpreter. The tapes hold the unchanged
description, a current-state record, a left-cell stack, a right-cell
stack, and a scratch record. Every work tape has a sentinel at cell
zero. A record is a finite unary block immediately to the right of its
sentinel, with the head returned to the sentinel between uses. A stack
consists of finitely many unary symbol blocks to the right of its
sentinel, written bottom to top, each block-end symbol also carrying an
origin bit; the head rests at the top block-end, or at the sentinel when
the stack is empty, and below the stored blocks the logical stack is
blank.
The routines are finite-control terminating scans:
copy a field: erase the old record, return to its sentinel, copy the
field's ones while scanning it;
compare a field with a record: scan their ones in parallel, remember
whether they end together, return the record head;
push: copy the scratch unary block after the top and append a block-end
with the chosen origin bit;
pop: remember the top origin bit in control, erase its end, walk its
ones backwards copying one to scratch per erased one, until the previous
end or the sentinel. An empty stack supplies blank index one and
origin bit zero.
Every scan stops on an explicitly present finite delimiter, so each
routine has finitely many control states.
Step 3: the loop. Initialize the state record from the description,
push the reversed input fields onto the right stack and mark its top
block as origin (for empty input push a marked blank), leave the left
stack empty. Each iteration: pop the right top into scratch, keeping
its bit; search the table for a row matching the state record and the
scratch record; on a match update the state record and scratch to the
next state and written symbol; then a right move pushes the written
symbol onto the left, a stay pushes it back onto the right, and a left
move pushes the written symbol right, then pops the left (an empty left
supplies a blank) and pushes that symbol right. Every push keeps the
appropriate origin bit. Return the description head to table-start and
repeat. If no row matches, restore the popped symbol and halt. The two
logical stacks are then exactly the interpreted tape halves, and the
origin bit recovers the absolute head position at every iteration.
Step 4: finitely many control states. Instruction location, comparison
outcome, origin bit, and chosen direction take finitely many values, and
unbounded interpreted indices stay in unary on the tape. Each character
test, write, copy or move is an ordinary finite transition, and the
finitely many call sites are inlined. Malformed descriptions may
receive arbitrary defaults; we only use valid ones.
Step 5: one tape. Encode the five aligned tracks on one two-sided tape
between a left and a right fence, with one head bit per track in the
product alphabet. At a simulated step, sweep the finite active interval
to collect the five scanned symbols into finite control; choose the
transition before changing any track; sweep to each head bit in turn and
make that track's write and move, leaving the other tracks alone; if a
head crosses a fence, replace the fence by a blank tuple with the new
head bit and put the new fence one cell farther out; return to the left
fence between sweeps. Only finitely many tracks, symbols and pending
choices are involved, so these are again finite rules; every sweep
terminates; and all data and head bits agree with the five-tape machine
at step boundaries. Halting is exactly the five-tape halting.
Step 6: consequences. This gives one fixed universal single-tape table.
The fluid compiler of Section 3 may therefore take either an arbitrary
finite machine table or this fixed table plus an input. Composing
Theorem A with a decision procedure for the fixed particle event would
decide halting; with the interpreter in place it would do so even with
the machine fixed and only the input varying. This includes Turing's
symbol-printing version: stop when a designated symbol is printed and
otherwise continue forever, including when the machine stops without
printing it. The construction asserts no uniform finite-precision
tolerance, because the codes are exact reals and the event is an open
set of them; it makes no claim about rounded arithmetic.
REFERENCES
C. H. Bennett, Logical reversibility of computation, IBM Journal of
Research and Development 17 (1973), no. 6, 525-532.
R. Cardona, E. Miranda and D. Peralta-Salas, Computability and Beltrami
fields in Euclidean space, Journal de Mathematiques Pures et Appliquees
169 (2023), 50-81.
R. Cardona, E. Miranda, D. Peralta-Salas and F. Presas, Constructing
Turing complete Euler flows in dimension 3, Proceedings of the National
Academy of Sciences 118 (2021), e2026818118.
S. Dyhr, A. Gonzalez-Prieto, E. Miranda and D. Peralta-Salas, Turing
complete Navier-Stokes steady states via cosymplectic geometry, PNAS
Nexus 5 (2026), pgag131.
R. Landauer, Irreversibility and heat generation in the computing
process, IBM Journal of Research and Development 5 (1961), no. 3,
183-191.
Y. Lecerf, Machines de Turing reversibles. Recursive insolubilite en
n in N de l'equation u = theta^n u, ou theta est un isomorphisme de
codes, Comptes rendus hebdomadaires des seances de l'Academie des
sciences 257 (1963), 2597-2600.
J. Leray, Sur le mouvement d'un liquide visqueux emplissant l'espace,
Acta Mathematica 63 (1934), 193-248.
C. Moore, Unpredictability and undecidability in dynamical systems,
Physical Review Letters 64 (1990), no. 20, 2354-2357.
C. Moore, Generalized shifts: unpredictability and undecidability in
dynamical systems, Nonlinearity 4 (1991), no. 2, 199-230.
A. M. Turing, On computable numbers, with an application to the
Entscheidungsproblem, Proceedings of the London Mathematical Society (2)
42 (1936-1937), 230-265.