Why completeness is pointwise, and why no decoder is needed

For a coordinate \(i\), let \(H_i=A_i+B_i\). The cut identity says

The last equation is pointwise. For every fixed accepted \(x\), at least one coordinate has \(D_i(x)=1\). The detecting coordinate may depend on \(x\) and may be an input, scratch, or target wire. The argument does not require a single fixed coordinate to detect all positives.

At an empty prefix, the direction is simply the target unit vector. At a full prefix, all non-target wires have restored and the target discrepancy is \(f\). Interior cuts can spread the direction through the workspace. These minimum cases verify the composition order and the role of the two target branches.

The zero-input cases are also valid. With only a target wire, the empty circuit realizes the constant-zero oracle and one NOT realizes the constant-one oracle. At every cut, the direction is nonzero and the discrepancy cover has the correct accepting set.

Essential hypothesis. The endpoint condition holds for both initial target values. The inverse-suffix derivation uses the branch \(b+f(x)\). Correctness only for initial target zero is not the stated model.

The theorem also does not require scratch to remain zero at the cut. Imposing that extra condition would exclude admitted restored circuits. Conversely, dropping target separation from the boundary encoding permits a vacuous endpoint equation: an encoding that ignores \(y\) can make the empty circuit appear to compute a nonzero function. The formal Boundary.target_eq property prevents precisely this degeneracy.

Permalink · Source line 69