Algorithm Examples - An Example: Algorithm Specification of Addition M+n

An Example: Algorithm Specification of Addition M+n

Choice of machine model:

There is no “best”, or “preferred” model. The Turing machine, while considered the standard, is notoriously awkward to use. And different problems seem to require different models to study them. Many researchers have observed these problems, for example:

“The principal purpose of this paper is to offer a theory which is closely related to Turing's but is more economical in the basic operations” (Wang (1954) p. 63)

“Certain features of Turing machines have induced later workers to propose alternative devices as embodiments of what is to be meant by effective computability.... a Turing machine has a certain opacity, its workings are known rather than seen. Further a Turing machine is inflexible ... a Turing machine is slow in (hypothetical) operation and, usually complicated. This makes it rather hard to design it, and even harder to investigate such matters as time or storage optimization or a comparison between efficiency of two algorithms.” (Melzak (1961) p. 281)

Shepherdson-Sturgis (1963) proposed their register-machine model because “these proofs are complicated and tedious to follow for two reasons: (1) A Turing machine has only one head... (2) It has only one tape....” They were in search of “a form of idealized computer which is sufficiently flexible for one to be able to convert an intuitive computational procedure into a program for such a machine” (p. 218).

“I would prefer something along the lines of the random access computers of Angluin and Valiant ” (Gurivich 1988 p. 6)

“Showing that a function is Turing computable directly...is rather laborious ... we introduce an ostensibly more flexible kind of idealized machine, an abacus machine...” (Boolos-Burgess-Jeffrey 2002 p.45).

About all that one can insist upon is that the algorithm-writer specify in exacting detail (i) the machine model to be used and (ii) its instruction set.

Atomization of the instruction set:

The Turing machine model is primitive, but not as primitive as it can be. As noted in the above quotes this is a source of concern when studying complexity and equivalence of algorithms. Although the observations quoted below concern the Random access machine model – a Turing-machine equivalent – the problem remains for any Turing-equivalent model:

“...there hardly exists such a thing as an ‘innocent’ extension of the standard RAM model in the uniform time measure; either one only has additive arithmetic, or one might as well include all multiplicative and/or bitwise Boolean instructions on small operands....” (van Emde Boas (1992) p. 26)

“Since, however, the computational power of a RAM model seems to depend rather sensitively on the scope of its instruction set, we nevertheless will have to go into detail...

“One important principle will be to admit only such instructions which can be said to be of an atomistic nature. We will describe two versions of the so-called successor RAM, with the successor function as the only arithmetic operation....the RAM0 version deserves special attention for its extreme simplicity; its instruction set consists of only a few one letter codes, without any (explicit) addressing.” (Schönhage (1980) p.494)

Example #1: The most general (and original) Turing machine – single-tape with left-end, multi-symbols, 5-tuple instruction format – can be atomized into the Turing machine of Boolos-Burgess-Jeffrey (2002) – single-tape with no ends, two "symbols" { B, | } (where B symbolizes "blank square" and | symbolizes "marked square"), and a 4-tuple instruction format. This model in turn can be further atomized into a Post-Turing machine – single-tape with no ends, two symbols { B, | }, and a 0- and 1-parameter instruction set ( e.g. { Left, Right, Mark, Erase, Jump-if-marked to instruction xxx, Jump-if-blank to instruction xxx, Halt } ).

Example #2: The RASP can be reduced to a RAM by moving its instructions off the tape and (perhaps with translation) into its finite-state machine “table” of instructions, the RAM stripped of its indirect instruction and reduced to a 2- and 3-operand “abacus” register machine; the abacus in turn can be reduced to the 1- and 2-operand Minsky (1967)/Shepherdson-Sturgis (1963) counter machine, which can be further atomized into the 0- and 1-operand instructions of Schönhage (and even a 0-operand Schönhage-like instruction set is possible).

Cost of atomization:

Atomization comes at a (usually severe) cost: while the resulting instructions may be “simpler”, atomization (usually) creates more instructions and the need for more computational steps. As shown in the following example the increase in computation steps may be significant (i.e. orders of magnitude – the following example is “tame”), and atomization may (but not always, as in the case of the Post-Turing model) reduce the usability and readability of “the machine code”. For more see Turing tarpit.

Example: The single register machine instruction "INC 3" – increment the contents of register #3, i.e. increase its count by 1 – can be atomized into the 0-parameter instruction set of Schönhage, but with the equivalent number of steps to accomplish the task increasing to 7; this number is directly related to the register number “n” i.e. 4+n):

More examples can be found at the pages Register machine and Random access machine where the addition of "convenience instructions" CLR h and COPY h₁,h₁ are shown to reduce the number of steps dramatically. Indirect addressing is the other significant example.