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 commercial 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 its speed at each iteration.

Confront a mathematician with this proposal; he will immediately point 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. Dijkstra
Department of Computer Sciences
The University of Texas at Austin
Austin, TX 78712-1188
United States of America

Transcribed by Michael Lugo

Last revised 25-May-2016 .