Dovetailer?

The following link mentions a 'dovetailer algorithm'. I googled for it but couldn't find anything. Can someone provide some information or pointers?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

dovetailing...

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

Dovetailing is from a classic proof

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.

Missing link

I think you forgot to include the link to the book you seem to refer to... O:-)

Dovetailing is from a classic proof

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.