TAOCP 1.1 Exercise 5
The exercise asks about the specific "Procedure for Reading This Set of Books" printed after the preface.
Exercise 5. ▶ [12] Show that the “Procedure for Reading This Set of Books” that appears after the preface actually fails to be a genuine algorithm on at least three of our five counts! Also mention some differences in format between it and Algorithm E.
Verified: yes
Solve time: 3m12s
The exercise asks about the specific "Procedure for Reading This Set of Books" printed after the preface. That procedure is intentionally written as advice to human readers, not as a formal algorithm. Using Knuth's five characteristics of algorithms from §1.1, one can show that it fails at least three of them.
Failure of definiteness
A genuine algorithm requires definiteness: every step must be stated precisely and unambiguously.
The reading procedure repeatedly appeals to the reader's personal judgment. It asks the reader to decide such things as:
- whether a topic is sufficiently understood;
- whether a section should be studied more carefully;
- which parts of the text deserve special attention;
- how much of the suggested material should be read.
These decisions are not specified by exact rules. Different readers could follow the instructions in different ways while honestly believing they were obeying the procedure. Hence the steps are not definite in Knuth's sense.
Failure of effectiveness
An algorithm must consist of elementary operations that can actually be carried out exactly.
The reading procedure contains actions such as understanding material, judging one's level of comprehension, deciding what is interesting or relevant, and choosing how to proceed based on that judgment. Such activities are intellectual processes, not elementary executable operations.
This objection is different from the failure of definiteness. Definiteness concerns ambiguity of instructions. Effectiveness concerns whether the prescribed operations are basic mechanical actions. Even if one tried to interpret the instructions consistently, operations like "understand the material" or "decide whether you know enough" are not elementary algorithmic steps.
Therefore the procedure fails the effectiveness requirement.
Failure of finiteness
An algorithm must terminate after a finite number of steps.
The reading procedure contains recommendations that permit repeated study whenever the reader feels additional work is needed. Progress through the procedure depends on subjective conditions such as satisfaction with one's understanding.
Because no objective criterion specifies when the reader must stop reviewing, revisiting, or studying a topic, the procedure does not guarantee termination. A reader might continue indefinitely, always deciding that further understanding is desirable.
Thus the procedure fails the finiteness requirement.
Other counts
The procedure does have inputs and outputs in a loose sense. The input is essentially a reader together with the books, and the intended output is a reader who has learned the material. Therefore the clearest failures are definiteness, effectiveness, and finiteness, which already satisfy the requirement of "at least three" counts.
Differences in format between the procedure and Algorithm E
The reading procedure also differs markedly in form from Algorithm E.
- Prose versus algorithmic layout.
The reading procedure is written as continuous English prose. Algorithm E is presented in the standard algorithmic format. 2. No numbered step labels.
Algorithm E is divided into labeled steps such as E1, E2, E3, etc. The reading procedure has no comparable step structure. 3. No explicit control flow.
Algorithm E contains precise transfers of control, conditions, and loops. The reading procedure uses informal advice rather than formally specified branching. 4. No assignments or symbolic variables.
Algorithm E manipulates variables by operations such as assignments and arithmetic computations. The reading procedure contains no variables, assignments, or symbolic state. 5. No explicit input-output specification.
Algorithm E has clearly identifiable data being processed and a well-defined result. The reading procedure only informally describes what the reader is expected to achieve. 6. No explicit termination step.
Algorithm E ends with a definite terminating condition. The reading procedure has no formally stated halting step.
Hence the "Procedure for Reading This Set of Books" is not a genuine algorithm. It fails at least the requirements of definiteness, effectiveness, and finiteness, and its format differs substantially from the structured presentation used in Algorithm E. ∎