Algorithm Characterizations - 1967 Rogers' Characterization

1967 Rogers' Characterization

In his 1967 Theory of Recursive Functions and Effective Computability Hartley Rogers' characterizes "algorithm" roughly as "a clerical (i.e., deterministic, bookkeeping) procedure . . . applied to . . . symbolic inputs and which will eventually yield, for each such input, a corresponding symbolic output"(p. 1). He then goes on to describe the notion "in approximate and intuitive terms" as having 10 "features", 5 of which he asserts that "virtually all mathematicians would agree " (p. 2). The remaining 5 he asserts "are less obvious than *1 to *5 and about which we might find less general agreement" (p. 3).

The 5 "obvious" are:

• 1 An algorithm is a set of instructions of finite size,
• 2 There is a capable computing agent,
• 3 "There are facilities for making, storing, and retrieving steps in a computation"
• 4 Given #1 and #2 the agent computes in "discrete stepwise fashion" without use of continuous methods or analogue devices",
• 5 The computing agent carries the computation forward "without resort to random methods or devices, e.g., dice" (in a footnote Rogers wonders if #4 and #5 are really the same)

The remaining 5 that he opens to debate, are:

• 6 No fixed bound on the size of the inputs,
• 7 No fixed bound on the size of the set of instructions,
• 8 No fixed bound on the amount of memory storage available,
• 9 A fixed finite bound on the capacity or ability of the computing agent (Rogers illustrates with example simple mechanisms similar to a Post-Turing machine or a counter machine),
• 10 A bound on the length of the computation -- "should we have some idea, 'ahead of time', how long the computationwill take?" (p. 5). Rogers requires "only that a computation terminate after some finite number of steps; we do not insist on an a priori ability to estimate this number." (p. 5).