Lambda the Ultimate

refers to single-stepping through multiple computations in such a way that each computation is ensured progress. in case of a finite number of computations this is easily done in round-robin style:

for i = 1 to infinity
for k = 1 to n
perform step i in computation k
possibly stop under certain conditions

however, dovetailing usually refers to the case of infinitely many computations, which requires some
a slightly different approach:

for i = 1 to infinity
for k = 1 to i
perform step i in computation k
possibly stop under certain conditions

%%!PS %% -John Tromp (http://www.cwi.nl/~tromp/)
42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlin

The name dovetailing stems from the proof that there is the same "number" of rationals as there are natural numbers.

Dovetailing is the way the rationals are number 1, 2, ...

See

for an explanation - notice especially the figure at page 4-5.

The name dovetailing stems from the proof that there is the same "number" of rationals as there are natural numbers.

Dovetailing is the way the rationals are number 1, 2, ...

See

http://www-courses.cs.uiuc.edu/~cs173/oldhtml/resources/MitchHarris/countability.ps

for an explanation - notice especially the figure at page 4-5.