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:

  1. First one has to read the N times displayed by the clocks,
  2. Then the average function of the N readings can be directly computed.

 

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:

 

  1. The computer must be universal in the sense that, once defined, its specifications are fixed once and for all.
  2. The universal computer should be able to solve Problem A for all values of N (a finite but unbounded positive integer) and at a moment T randomly selected by the problem poser.
  3. There is no limit on the size of the memory your universal computer can have.
  4. There is no limit on the amount of time your universal computer takes to solve Problem A.
  5. The only limit is on the number of basic operations (read, write, add, etc.) that your universal computer can perform per tick: this must be a finite constant.
  6. Solutions invoking time travel or divine intervention are beyond the scope of this challenge.

 

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)."