Definition
Dovetailing
Dovetailing interleaves a sequence of computations
that can be generated and simulated effectively. One sequential schedule is At stage
, advance each listed unfinished computation by one step, in order, resuming from its saved state. Each stage is finite, and
advances at every stage until it halts. Thus every non-halting computation receives arbitrarily many steps, every halting computation is eventually detected, and none blocks the others. First five stages with no computation halted yet; orange tracks the successive steps of
.
Intuition
Give each computation another turn
Each
is a program running on an input. Suppose never halts, but halts after two instructions. Each cell below is one instruction on a single processor. Between turns, retain each computation’s state: for a URM, its instruction position and registers. A stage is one finite round, including one new computation. We find
‘s result without making terminate or deciding that it never will.