Bounded-overhead tie normalization for fair-bit machines

At the fixed input let $R=R(n)$ and let $A$ count accepting strings among the $2^R$ fair-bit strings, including unused suffixes after early halting; then $p=A\mathrm{/}{2}^R$ by [F1]. The new machine first reads $R+2$ selector bits, rejecting only the all-zero selector. On every nonzero selector it simulates the original machine for at most $R$ steps using $R$ fresh bits, records its outcome, and consumes any unused suffix bits in a no-op state. On the zero selector it consumes all $R$ fresh bits and rejects. By [F3] this is a well-defined clocked procedure. There are exactly $2^{2R+2}$ equiprobable strings and exactly $(2^{R+2}-1)A$ accepting ones, so $p^{\mathrm{\prime }}=(1-2^{-(R+2)})p$.

If $p\le 1\mathrm{/}2$ then $p^{\mathrm{\prime }}<1\mathrm{/}2$. If $p>1\mathrm{/}2$, then $A\ge 2^{R-1}+1$, so $p-1\mathrm{/}2\ge 2^{-R}$; because $p\le 1$, $p^{\mathrm{\prime }}-1\mathrm{/}2=(p-1\mathrm{/}2)-p{2}^{-(R+2)}\ge 2^{-R}-2^{-(R+2)}>0$. Thus strict majority is preserved and an original tie becomes a strict no-instance.

The new acceptance probability cannot equal one half: such equality would require the integer $A$ to equal $2^{2R+1}\mathrm{/}(2^{R+2}-1)$, which is not an integer because its denominator is odd and greater than one. Since no tie remains, swapping accepting and rejecting labels makes the complement machine accept strictly above one half exactly on the original no-instances. The selector and padding add $2R+2$ transitions, so the overhead is $O(R(n))$.