A Computational Challenge (by S.G. Akl)
On a limestone wall, N clocks are hanging. There are at least two clocks. The clocks are digital, each displaying the time as a quadruple of digits WX:YZ; for example, 19:48. All the clocks are working, ticking away synchronously (even as you read this challenge). However, they are not working as you might expect: At every tick, each clock displays a new, but random, quadruple WX:YZ—a time perhaps different from the ones displayed by the other N-1 clocks. No clock has a memory; therefore, when at the following tick a new time is generated and displayed, the previous quadruple is lost forever. The limestone wall is long at will, allowing N to be big at will.
Problem A: For an arbitrary number of clocks N, it is required to compute the average of the N times displayed at a given moment T.
This problem is easily solvable, at least in theory:
The problem is also readily solvable in practice by a special-purpose computer, provided that the latter is available at time T (the details of such computer are deliberately omitted here). Note that in order to make the problem feasible, it is implicitly assumed that the moment T at which the problem poser asks for the average to be computed occurs within any tick of the clocks after the problem solver declares being ready (this eliminates the possibility of the problem poser asking for the average of the times displayed by the clocks at a time prior to the moment the problem solver declares being ready). It is also important to keep in mind that the problem solver does not know N before declaring being ready.
Now, on to the challenge. A universal computer is a computer that is capable of computing any computable function.
Computational Challenge: Design a universal computer that solves Problem A.
A valid solution must satisfy the following conditions:
If you solve the challenge, please let me know (akl at cs period queensu period ca). Otherwise, read this.
And now for some humor. Below are two of a number of humorous solutions I received.
I. "I would wait until all but two of those clocks run out of battery power, leaving me enough time to read the remaining two clocks and compute the average time. ;-) Note that battery lifetime does not go up as N increases, so this algorithm will indeed work.
What, these clocks are plugged in, not on batteries? Then I would need to construct a pull-the-plug robot, a more difficult problem."
II. "Let's imagine a computational system that consists of the following:
1. A typewriter
2. A monkey typing randomly at a fixed speed
3. An educated computer system engineer, able to interpret anything readable what the monkey has typed and follow the instructions.
Given infinite amount of time, paper and engineer's patience I think the monkey is almost surely able to write the design specification for a computer system solving "problem A" for any given N. Hopefully the engineer would be able to build this system within a finite amount of time and budget limit (which is dependent on N of course)."