The Setting
Take a randomized machine that halts within steps on an input , whatever its coins, and accepts with probability . Error reduction for one-sided error runs a second time on fresh coins and accepts when either trial accepts. In small space the two trials run side by side on separate tapes, and the single stream of coins, one bit per step, has to be shared out between them. The question is how to build the pair as one machine, and what it costs in time and space and gains in acceptance probability.
Machines, Runs and Coins
An input is a binary word of length . An input symbol is the left endmarker, a bit, or the right endmarker, and the input tape of has cells.✦
A randomized machine with states , work tapes indexed by and input heads indexed by consists of a start state , a set of halting states, each accepting or rejecting, and a transition function; each work tape has one head, and each input head reads the input tape.✦ An action of is a next state together with a bit to write on each work tape and a direction (left, stay or right) for each work head and each input head.✦ The transition function maps a state, the input symbols under the input heads, the bits under the work heads and a coin bit to an action.
A configuration of on inputs of length consists of a state, one of the input cells for each input head, an integer position for each work head, and the contents of each work tape, a bit at every integer cell.✦
A coin tape is an infinite sequence of coin bits, one for each time step.✦ The initial configuration of on is the configuration in the start state with each input head on the left endmarker, each work head at position and every work cell holding . The run of on with coin tape is the sequence of configurations , , that starts at the initial configuration and passes from to by one step of with coin .✦ The machine halts on within steps if is in a halting state for every coin tape ; is the set of such inputs.✦
For a bit string , the coin tape of has coin at each time and coin from time on.✦ The acceptance probability of on at time is the fraction of the strings whose run is in an accepting state after steps: (1)✦
When has finitely many work tapes, the space it uses on with coin tape through time counts, for each work tape, the cells its head visits up to time : (2)✦ where is the position of the head of work tape in the configuration .
The Doubled Machine
The doubled machine runs two copies of on one coin tape. Its states are triples of two states of and a coin register , empty or holding one bit; its work tapes and input heads are two disjoint copies of those of , the first driven by and the second by . It starts in . A state is halting when and both and are halting, and it is accepting when moreover or is accepting.
The transitions of are built from two actions of . At a state , the idle action keeps , writes back the bits under the work heads and moves no head✦; the stuttering step at is the step of when is not halting and the idle action when it is.✦ From a state with coin , stores the coin: it passes to by an idle action. From with coin , it takes the combined action of the first copy’s stuttering step from with coin and the second copy’s from with coin : each copy writes and moves its own tapes and heads, and the register empties.
The even and odd coin tapes of a coin tape are (3)
For configurations and of on inputs of length and a register value , the joined configuration is the configuration of in the state , with and the states of and , whose first copy of heads and tapes is as in and whose second copy is as in .✦
The Claim
Theorem 1. Let be a randomized machine, a binary word and . For every coin tape , (4)✦ and, if has finitely many work tapes, (5)✦ If halts on within steps, then (6)✦ and (7)✦
What Is Checked
The claim is stated over randomized machines with input heads on an endmarked input tape and binary work tapes infinite in both directions, their configurations and runs on a coin tape, halting within steps, the acceptance probability (1), the space (2), and the doubled machine with the even and odd coin tapes (3) and the joined configuration.