Automata and computation

Abelian gates and chronology erasure

This program asks when a computation can forget execution order without losing the behavior that matters. Its main mathematical target became floor depth for abelian logic gates; boundary receipts remain a supporting method rather than the program's conclusion.

Research question

Holroyd, Levine, and Winkler define a hierarchy $R_0\subseteq R_1\subseteq\cdots$ by starting with nonnegative affine functions and repeatedly closing under addition and integer floors. They prove that every $k$ -input ZILP function has floor depth at most $k$ and ask whether that bound is sharp.

The first bounded FPRD target was the complete binary alternative: exhibit $f\in R_2\setminus R_1$ , or prove that every binary ZILP function lies in $R_1$ . The paper supplies the question and the upper bound; the separation below is proved by FPRD Lab.

AFD-11 · theorem

A binary ZILP function of exact floor depth two

Theorem. The function

$f(x,y)=\left\lfloor\frac{x}{3}\right\rfloor+\left\lfloor\frac{y}{3}\right\rfloor+\mathbf 1_{\{x\equiv y\equiv2\pmod3\}}$

is an increasing binary ZILP function in $R_2\setminus R_1$ .

Proof structure. Its horizontal increment support modulo three is the noncollinear set $H=\{(2,0),(2,1),(1,2)\}$ . A primitive depth-one floor term with positive horizontal coefficient has every nonempty horizontal pulse fiber projecting modulo three to an affine line or the whole torus. Positivity of the $R_1$ normal form prevents cancellation outside $H$ , so no depth-one representation exists.

Direct membership in $R_2$ is witnessed by $f(x,y)=\left\lfloor\frac{\lfloor2x/3\rfloor+\lfloor2y/3\rfloor}{2}\right\rfloor.$ The finite period-three search found the candidate; the all-denominator pulse-fiber argument carries the lower bound.

UPT-01 · universal invariant

Unprimed acyclic networks are superadditive

Lemma. Every scalar function computed by a finite acyclic network of splitters, adders, and unprimed topplers obeys $F(x+y)\ge F(x)+F(y).$

Coordinate functions are additive; addition preserves superadditivity; and $F\mapsto\lfloor F/\lambda\rfloor$ preserves it because $\left\lfloor\frac{F(x)+F(y)}{\lambda}\right\rfloor\ge\left\lfloor\frac{F(x)}{\lambda}\right\rfloor+\left\lfloor\frac{F(y)}{\lambda}\right\rfloor.$ Induction through the acyclic syntax proves the result at every depth. It concerns aggregate input counts, not trace order, timing, queues, or odometers.

UPT-02 · counterexample

The published sign condition is not sufficient

The unary increasing ZILP function $h(n)=n-\mathbf 1_{\{n\equiv2\pmod3\}}$ has the required form $L+P$ with periodic $P\le0$ , but $h(2)=1<2h(1)=2$ . Therefore it is excluded from every unprimed acyclic network by superadditivity. Priming computes it as $h(n)=\left\lfloor\frac n3\right\rfloor+\left\lfloor\frac{2n+1}{3}\right\rfloor,$ so the obstruction genuinely distinguishes the unprimed syntax.

UPT-03 · exact classification

The unary residual-period-three class

Let $f:\mathbb N\to\mathbb N$ be zero at zero with periodic residual of period dividing three, and put $A=f(3),\ a=f(1),\ b=f(2)$ . The following are equivalent: unprimed-DAG computability; superadditivity; the inequalities $2a\le b$ and $2b\le A+a$ ; and the one-layer formula

$f(n)=an+(A+a-2b)\left\lfloor\frac n3\right\rfloor+(b-2a)\left\lfloor\frac{2n}{3}\right\rfloor.$

Necessity follows by applying superadditivity to $1+1=2$ and $2+2=4$ . Under those inequalities the displayed coefficients are nonnegative, and checking the three residue classes proves sufficiency.

UPT-04 · minimal-period result

Period three is the first unary sign-only failure

For residual period dividing two, writing $A=f(2)$ and $a=f(1)$ , the condition $P\le0$ is exactly $A\ge2a$ , and $f(n)=an+(A-2a)\left\lfloor\frac n2\right\rfloor$ is an unprimed formula. Period one is affine, so period three is the smallest unary coordinate period where the sign condition alone fails.

Open questions

The binary witness resolves the selected two-input target, not the all-arity sharpness question.
The unprimed classification is unary and period at most three; arbitrary periods and multiple inputs remain open.
Finite checks corroborate the formulas but are not the proofs.

A useful next step is to compare the depth-two separation and the unprimed obstruction with the existing literature before extending the argument to broader cases.