Algorithm Characterizations - 1972 Stone's Characterization

1972 Stone's Characterization

Stone (1972) and Knuth (1968, 1973) were professors at Stanford University at the same time so it is not surprising if there are similarities in their definitions (boldface added for emphasis):

"To summarize ... we define an algorithm to be a set of rules that precisely defines a sequence of operations such that each rule is effective and definite and such that the sequence terminates in a finite time." (boldface added, p. 8)

Stone is noteworthy because of his detailed discussion of what constitutes an “effective” rule – his robot, or person-acting-as-robot, must have some information and abilities within them, and if not the information and the ability must be provided in "the algorithm":

"For people to follow the rules of an algorithm, the rules must be formulated so that they can be followed in a robot-like manner, that is, without the need for thought... however, if the instructions are to be obeyed by someone who knows how to perform arithmetic operations but does not know how to extract a square root, then we must also provide a set of rules for extracting a square root in order to satisfy the definition of algorithm" (p. 4-5)

Furthermore "...not all instructions are acceptable, because they may require the robot to have abilities beyond those that we consider reasonable.” He gives the example of a robot confronted with the question is “Henry VIII a King of England?” and to print 1 if yes and 0 if no, but the robot has not been previously provided with this information. And worse, if the robot is asked if Aristotle was a King of England and the robot only had been provided with five names, it would not know how to answer. Thus:

“an intuitive definition of an acceptable sequence of instructions is one in which each instruction is precisely defined so that the robot is guaranteed to be able to obey it” (p. 6)

After providing us with his definition, Stone introduces the Turing machine model and states that the set of five-tuples that are the machine’s instructions are “an algorithm ... known as a Turing machine program” (p. 9). Immediately thereafter he goes on say that a “computation of a Turing machine is described by stating:

"1. The tape alphabet

"2. The form in which the parameters are presented on the tape

"3. The initial state of the Turing machine

"4. The form in which answers will be represented on the tape when the Turing machine halts

"5. The machine program" (italics added, p. 10)

This precise prescription of what is required for "a computation" is in the spirit of what will follow in the work of Blass and Gurevich.