The Art of Computer Programming/Algorithms

Notes on Page 7

This page is part of The Art of Computer Programming.

Explanation of "f is a function from Q into itself" and "f(q) should equal q for all elements q of (horseshoe symbol)" from p. 7.

The problem on page seven where Knuth attempts to explain algorithms in terms of mathematical set theory is giving me big trouble though. Specifically, can anyone explain the following statements?

"f is a function from Q into itself". "f(q) should equal q for all elements q of (horseshoe symbol)"

It actually gets a little clearer as you read further along through the example.

While studying anything in depth, one builds a model of the subject, in which everything that is non-essential is stripped away, and only core concepts are retained. This allows one to analyze the subject in a mathematically rigorous manner, without any ambiguities that might arise from an informal description.

In this case, Knuth is building a model to represent a "computational method" by abstracting away real-world things such as CPUs, memory, displays and suchlike.

Q represents all the possible states that a computation may be in. Of these, some states can be considered as input states (I), and some as output states (the horseshoe symbol, which is the uppercase Greek letter Omega). And then there is the function f which represents a computational step.

Given that you are currently in state x of the computation, if you apply step f, you get into a new state y. If you are already in an output state (in other words, if you have finished the computation), applying step f again doesn't get you anywhere. You just stay in the same state -- that's what "f(q) should equal q for all elements q of Omega" means.

Let's say you want to use an elevator to get to the 3rd floor in a five-floor building. The set Q has five states:

1) Elevator in floor 1
2) Elevator in floor 2
3) Elevator in floor 3
4) Elevator in floor 4
5) Elevator in floor 5

The set I also has the same 5 states since you can get into an elevator from any floor.

Suppose that floor 4 is a private suite, so you can't get off at floor 4. In that case, Omega will include only states (1, 2, 3, 5) from Q. Note that people on the fourth floor can summon the elevator to their floor, so 4 is still in set I.

Function f is the act of pressing a button inside the elevator.

Now the statement f(q) = q says that if are already on floor 2, then pressing 2 again leaves you in the same state. That's all. The reason you have to specify this in the model is to define termination of the computation method rigorously.

Note that the model does not need to specify memory as a distinct concept because it can be rolled into the notion of a state. In the Euclid's algorithm example on page 8, Knuth has used state variables 1, 2 and 3 to represent different states of the computation, but he has included it as part of the states. If you were to write it in a programming language, you'd either use explicit state variables, or it would be implicit in the form of the program counter. (The program counter and the registers in a CPU are all part of the computer's state.)

I hope this has made it somewhat clearer. In general, you don't really need to go back to such a primitive definition of a computational method, but it is useful to have such a definition around, just in case someone asks, "But what exactly do you mean by 'computational method'?"