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:
Good luck!
If you solve the
challenge, please let me know (akl at cs period queensu period ca). Otherwise,
read this.
Humor
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)."