Algorithm Characterizations - 2002: Boolos-Burgess-Jeffrey Specification of Turing Machine Calculation

2002: Boolos-Burgess-Jeffrey Specification of Turing Machine Calculation

For examples of this specification-method applied to the addition algorithm "m+n" see Algorithm examples.

An example in Boolos-Burgess-Jeffrey (2002) (pp. 31–32) demonstrates the precision required in a complete specification of an algorithm, in this case to add two numbers: m+n. It is similar to the Stone requirements above.

(i) They have discussed the role of "number format" in the computation and selected the "tally notation" to represent numbers:

"Certainly computation can be harder in practice with some notations than others... But... it is possible in principle to do in any other notation, simply by translating the data... For purposes of framing a rigorously defined notion of computability, it is convenient to use monadic or tally notation" (p. 25-26)

(ii) At the outset of their example they specify the machine to be used in the computation as a Turing machine. They have previously specified (p. 26) that the Turing-machine will be of the 4-tuple, rather than 5-tuple, variety. For more on this convention see Turing machine.

(iii) Previously the authors have specified that the tape-head's position will be indicated by a subscript to the right of the scanned symbol. For more on this convention see Turing machine. (In the following, boldface is added for emphasis):

"We have not given an official definition of what it is for a numerical function to be computable by a Turing machine, specifying how inputs or arguments are to be represented on the machine, and how outputs or values represented. Our specifications for a k-place function from positive integers to positive integers are as follows:

"(a) The arguments m₁, ... m_k, ... will be represented in monadic notation by blocks of those numbers of strokes, each block separated from the next by a single blank, on an otherwise blank tape.

Example: 3+2, 111B11

"(b) Initially, the machine will be scanning the leftmost 1 on the tape, and will be in its initial state, state 1.

Example: 3+2, 1₁111B11

"(c) If the function to be computed assigns a value n to the arguments that are represented initially on the tape, then the machine will eventually halt on a tape containing a block of strokes, and otherwise blank...

Example: 3+2, 11111

"(d) In this case the machine will halt scanning the left-most 1 on the tape...

Example: 3+2, 1_n1111

"(e) If the function that is to be computed assigns no value to the arguments that are represented initially on the tape, then the machine either will never halt, or will halt in some nonstandard configuration..."(ibid)

Example: B_n11111 or B11_n111 or B11111_n

This specification is incomplete: it requires the location of where the instructions are to be placed and their format in the machine--

(iv) in the finite state machine's TABLE or, in the case of a Universal Turing machine on the tape, and

(v) the Table of instructions in a specified format

This later point is important. Boolos-Burgess-Jeffrey give a demonstration (p. 36) that the predictability of the entries in the table allow one to "shrink" the table by putting the entries in sequence and omitting the input state and the symbol. Indeed the example Turing machine computation required only the 4 columns as shown in the table below (but note: these were presented to the machine in rows):