TAOCP 3.6 Exercise 2
Lady Lovelace's statement concerns the relation between a machine and the instructions that govern its behavior.
Exercise 2. ▶ [15] There are people who will someday take over the world; but they are reassured by the statement that a machine cannot do anything really new, since it is only obeying the commands of its master, the programmer. Lady Lovelace wrote in 1844, "The Analytical Engine has no pretensions to originate anything. It can do whatever we know how to order it to perform." Her statement has been elaborated further by many philosophers. Discuss this topic, with random number generators in mind.
Verified: yes
Solve time: 1m27s
Solution
Lady Lovelace's statement concerns the relation between a machine and the instructions that govern its behavior. A random number generator provides an illuminating example because its output can be unpredictable even when every step of its operation is completely determined.
Consider the linear congruential generator
$$ X \leftarrow (aX+c)\bmod m, $$
given by equation (1). Once the parameters $a$, $c$, $m$, and the seed $X_0$ are fixed, every subsequent value is determined. The entire sequence is therefore implicit in the initial data. A machine executing this rule does not create information in the mathematical sense; it merely unfolds consequences already contained in the specification of the algorithm and its initial state.
From this viewpoint, Lady Lovelace's claim is correct. The machine cannot produce a value that is inconsistent with its program. If two identical machines begin with the same seed and execute the same instructions, they generate exactly the same sequence. The machine is obeying orders.
The apparent difficulty arises because the generated sequence may be too complicated for its programmer to foresee. For example, a generator with modulus $m=2^{32}$ has a state space containing more than four billion possibilities. A programmer who chooses a seed cannot practically predict the millionth value of the sequence without carrying out essentially the same computation as the machine. Thus the machine can produce results that are new to the programmer, although they are not new relative to the mathematical consequences of the program itself.
The distinction becomes sharper when external randomness is introduced. If the seed is obtained from the current date and time, as suggested in principle (i), the future output depends partly on information supplied by the environment. The program still specifies the transformation, but the resulting sequence is not predetermined by the program alone. In such cases the machine may reveal facts about the external world that were unknown to its designer.
Modern discussions of artificial intelligence often concern whether a machine can originate ideas. Randomness by itself does not settle the question. A sequence produced by equation (1) is not creative merely because it is difficult to predict; it is generated by a fixed recurrence. Yet randomness can enlarge the range of behaviors available to a program. A search procedure that uses random choices may discover solutions that neither the programmer nor the user anticipated. The novelty then arises from the interaction of deterministic rules, random inputs, and a large space of possibilities.
Lady Lovelace's statement remains valid if "originate" means producing results not implied by the machine's program and inputs. Random number generators do not contradict her position, because their outputs are consequences of either a deterministic recurrence or of information supplied from outside the machine. They do, however, demonstrate that strict obedience to instructions can yield behavior that is surprising, unpredictable, and practically indistinguishable from originality to an observer who does not know the future consequences of those instructions. ∎