FPRD-T171: Finite obstruction duality for causal selection

1. The finite candidate universe

Let $A\subseteq\widehat\Sigma^*$, and let

$$\pi:\widehat\Sigma\to\Sigma$$

be a letter projection between finite alphabets. Fix a selector-count budget $m$ and a selector-state budget $s$.

Write $a=|\Sigma|$ and $h_x=|\pi^{-1}(x)|$. The number of labeled synchronous selectors with exactly $r$ states and a fixed initial state is

$$r^{ra}\left(\prod_{x\in\Sigma}h_x\right)^r.$$

Indeed, for every state-input pair the transition chooses one of $r$ next states and one output from the appropriate fiber $\pi^{-1}(x)$. Hence the number of selector descriptions with at most $s$ states is

$$M_s(\pi)= \sum_{r=1}^{s} r^{ra}\left(\prod_{x\in\Sigma}h_x\right)^r.$$

Repeated copies of one selector do not improve a cover. Therefore the number of nonempty candidate families containing at most $m$ selectors is bounded by

$$N_{m,s}(\pi)= \sum_{j=1}^{\min(m,M_s(\pi))} \binom{M_s(\pi)}{j}.$$

Different labeled descriptions may compute the same selector, so this is a uniform upper bound rather than a minimal behavioral count.

2. FPRD-T171: finite obstruction certificates

Assume

$$(m,s)\notin\operatorname{Sel}(A,\pi).$$

Then there is a finite set $W\subseteq\pi(A)$ with

$$|W|\le N_{m,s}(\pi)$$

such that every family of at most $m$ selectors, each with at most $s$ states, fails to select an accepting lift for at least one word in $W$.

Conversely, the existence of such a finite obstruction set proves $(m,s)\notin\operatorname{Sel}(A,\pi)$.

Proof

There are at most $N_{m,s}(\pi)$ candidate families. A candidate family that is not a global cover misses some word of $\pi(A)$. Choose one missed word for each candidate family and remove duplicates. The resulting set W has the required size and defeats every family. The converse is immediate.

This argument uses projection compatibility. A selector cannot create a false positive: if its selected lift belongs to $A$, the observed word necessarily belongs to $\pi(A)$. Failure of equality is therefore always witnessed by a missed accepted word.

3. Exact failure-set duality

Let $\mathcal F_{m,s}$ be the finite candidate-family universe. For each accepted observed word $w$, define

$$D_w= \{F\in\mathcal F_{m,s}:F\text{ misses }w\}.$$

Then

$$(m,s)\notin\operatorname{Sel}(A,\pi) \quad\Longleftrightarrow\quad \bigcup_{w\in\pi(A)}D_w=\mathcal F_{m,s}.$$

The least cardinality of an obstruction set is exactly the minimum set-cover number of this failure system. Define it by

$$\omega_{A,\pi}(m,s) =\min\{|W|:W\subseteq\pi(A), \ \bigcup_{w\in W}D_w=\mathcal F_{m,s}\}.$$

For an infeasible budget,

$$1\le\omega_{A,\pi}(m,s)\le N_{m,s}(\pi).$$

As resources increase, obstruction cardinality cannot decrease: any set that defeats a larger candidate universe also defeats every smaller one.

4. Escape length is the optimal obstruction radius

For an infeasible budget, FPRD-T169 defines

$$e_{A,\pi}(m,s) =\min\{n:(m,s)\notin\operatorname{Sel}_n(A,\pi)\}.$$

T171 gives the exact certificate interpretation

$$e_{A,\pi}(m,s) = \min_W\max_{w\in W}|w|,$$

where W ranges over all finite obstruction sets for the budget.

If W has maximum word length L, it already proves failure through horizon L, so $e\le L$. Conversely, all accepted words of length at most e form a finite obstruction set, so the optimal obstruction radius is at most e.

Thus T169 and T171 measure two different aspects of one finite certificate:

• $e$ is its smallest possible radius;
• $\omega$ is its smallest possible number of test words.

5. Consequence for the hard visible lift

For the visible lift $A_C$ from FPRD-T168,

$$\operatorname{Sel}(A_C,\pi)=\varnothing.$$

Therefore every finite pair $(m,s)$ has a finite obstruction suite $W_{m,s}$ satisfying

$$|W_{m,s}|\le N_{m,s}(\pi), \qquad \max_{w\in W_{m,s}}|w| \ge e_{A_C,\pi}(m,s).$$

An optimized suite attains equality in the radius. This does not construct the suite for the Kim-Park witness or bound the lengths of its words.

6. Limits

• The theorem is existential. It does not make obstruction suites computable when membership in A is not decidable.
• The cardinality bound can be very loose because it counts labeled machines rather than distinct selector behaviors.
• Word lengths remain unbounded by the finite candidate count.
• The theorem concerns finite-state synchronous selectors. It does not cover unbounded-memory or asynchronous strategies.
• The hard-lift application retains the imported separation premise recorded in FPRD-T168.

The argument is finite set-cover duality applied to a finite automaton universe. No literature-priority claim is made without specialist review.