Home

Feedback

FAQ

Getting Started

Discussions

Site operation discussions

Recent Posts

(new topic)

Departments

Courses

Research Papers

Design Docs

Quotations

Genealogical Diagrams

Archives

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

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.

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

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

## Recent comments

23 hours 27 min ago

2 days 18 hours ago

1 week 6 days ago

2 weeks 5 days ago

3 weeks 5 days ago

5 weeks 4 days ago

5 weeks 6 days ago

7 weeks 17 hours ago

7 weeks 4 days ago

7 weeks 4 days ago