Models of computation

Finite-horizon fitting and resource escape

A model may match every finite observation of a target without admitting one exact presentation at the same resource bound. Presentation demand fields record that distinction. Compactness tells us when the finite fits sew together; escape moduli describe how they fail when no fixed compact family contains them.

FPRD-D28 · definition

Presentation demand fields

Let $X$ be a Hausdorff space of target behaviors. A bounded-observation tower consists of spaces $X_N$ and compatible observation maps $q_N:X\to X_N$ . We assume that the observations separate points and that the matching cylinders

C_N(x)=q_N^{-1}(q_N(x))

form a neighborhood basis at each target.

A presentation doctrine supplies presentations $P$ , their semantics $\llbracket P\rrbracket\in X$ , and a resource value $\kappa(P)$ in a partially ordered set. The resource may depend on the presentation, but not on the target or observation horizon. Its semantic stratum is

S_r=\{\llbracket P\rrbracket:\kappa(P)\le r\}.

For a target $x$ , resource bound $r$ , and horizon $N$ , define

K_{x,r,N}=\{y\in S_r:q_N(y)=q_N(x)\}, \qquad F_x(N)=\{r:K_{x,r,N}\ne\varnothing\},

F_x(\infty)=\{r:x\in S_r\}.

The set-valued map $N\mapsto F_x(N)$ is the presentation demand field. Its Pareto boundary retains incomparable resources that a scalar minimum would erase.

The first obstruction at fixed resource is $\omega_x(r)=\min\{N:K_{x,r,N}=\varnothing\}$ . If $S_{r,t}\uparrow S_r$ is an increasing compact exhaustion, the corresponding escape modulus is

e_x(r,t)=\min\{N:q_N(x)\notin q_N(S_{r,t})\},

with value $\infty$ when no such horizon exists.

FPRD-T60 · theorem

Finite-horizon fitting is closure membership

r\in\bigcap_{N\ge0}F_x(N) \quad\Longleftrightarrow\quad x\in\overline{S_r}.

Indeed, the left side says that every cylinder $C_N(x)$ meets $S_r$ . Because those cylinders form a neighborhood basis, this is exactly the definition of closure membership.

If $S_r$ is compact, it is closed in the Hausdorff space $X$ . Hence finite feasibility through every horizon implies $x\in S_r$ : one exact presentation exists at that resource bound.

For nested compact strata indexed by natural numbers, if $d_x(N)=\min F_x(N)$ , then

d_x(\infty)=\sup_N d_x(N).

The closure equivalence uses the cylinder-basis hypothesis. Compactness is a sufficient condition for sewing because it makes the fixed stratum closed; it is not automatic for every resource measure.

FPRD-T61 · theorem

Failed sewing is escape from every compact core

For an increasing compact exhaustion of one stratum,

e_x(r,t)=\infty \Longleftrightarrow x\in S_{r,t},

r\in\bigcap_N F_x(N) \Longleftrightarrow \sup_t e_x(r,t)=\infty,

r\in F_x(\infty) \Longleftrightarrow \exists t\;e_x(r,t)=\infty.

Thus finite fits exist at every horizon but no exact fit exists at resource $r$ precisely when every compact core has a finite escape horizon while those horizons are unbounded across the exhaustion.

If $y_N$ fits the target through horizon $N$ , then after $N\ge e_x(r,t)$ it cannot lie in the fixed core $S_{r,t}$ . The departure conclusion applies to horizon-fitting sequences, not to arbitrary sequences of presentations.

Compact cores for integer max-plus machines

The max-plus example below uses finite sequential machines over integer weights. Trim the machine, push the weight of a fixed breadth-first access word into each state, and absorb the initial weight. This gauge transformation preserves the computed series.

The canonical height is the largest absolute transition or final weight after this normalization. With cover width, total state count, and canonical height fixed, only finitely many normalized integer machines exist. These finite sets provide the compact cores used by the escape theorem.

Raw weights before gauge normalization do not measure the same resource. The finiteness argument also does not extend unchanged to arbitrary rational or real weights.

FPRD-T62 · theorem and exact calibration

The max-count series has an exact finite-horizon frontier

Over the alphabet $\{a,b\}$ , let

F(w)=\max(|w|_a,|w|_b).

The two functions $|w|_a$ and $|w|_b$ are computed by one-state sequential machines, so their maximum is an exact width-two cover with resource $(2,2,1)$ . No single finite sequential component computes $F$ exactly.

Exact horizon-N minimum.

s_1(N)=2\lfloor N/2\rfloor+1, \qquad h_1(N)=\lfloor N/2\rfloor,

where $s_1$ is minimum width-one state count and $h_1$ is minimum canonical height.

For the upper bound, track the signed difference $|w|_a-|w|_b$ , clamped to $[-h,h]\cap\mathbb Z$ . The tracker has $2h+1$ states and canonical height $h$ . It is exact through horizon $2h+1$ and first fails on $a^{h+1}b^{h+1}$ .

Conversely, distinct signed differences that can be separated by a short suffix must occupy distinct states, yielding the state lower bound. Gauge-normalized path differences force canonical height at least $\lfloor N/2\rfloor$ . Both width-one coordinates therefore escape linearly:

(1,\Theta(N),\Theta(N)) \quad\text{versus the exact resource}\quad (2,2,1).

Cover width is not run ambiguity. The result does not assert tropical 2-ambiguisability. Nor does growth across width-one resource bounds by itself create a sewing defect at one fixed fine resource.

Scope and open questions

Find natural noncompact strata with a genuine fixed-resource sewing defect.
Determine when compactness can be replaced by direct closedness of a semantic stratum.
Compare Pareto demand fields with established approximation and weighted-automata complexity measures.
Extend compact-core arguments beyond integer weights without silently assuming finiteness.

Sources

The FPRD proofs have been internally reconstructed and checked. No documented external or specialist review of these FPRD results is recorded.