A computer to think about

We all know of the possibility of starting a computer on a nonterminating repetition. This possibility is unfortunate because with the commerical equipment currently available, such a program takes an awful lot of time to execute it. I therefore propose a machine that needs 1 second for the first iteration and furthermore doubles the speed at each iteration.

Confront a mathematician with this proposal: he will immediately pont out that your proposal is logically flawed: in what state will your machine be 2+ε sec. after it was started? Contradiction!

Show it to a physicist that knows his good, old Einstein; he immediately sees that, due to the finite velocity of light, one should implement the doubling of the speed by halving the size of the machine at each iteration. Then, after 2 seconds, the contradiction has disappeared, and so has your machine (but that is only fair: any computer irrevocably embarked upon a nonterminating computation is effectively lost).

Nuenen, 3 July 1985

prof. dr. Edsger W. Dykstra
Department of Computer Sciences
The University of Texas at Austin
AUSTIN, Texas 78712-1188
United States of America


Transcribed by Michael Lugo

Last revised Sat, 29 May 2004.