Algorithm Examples - Example: Counter-machine Versus Turing-machine Computation

Example: Counter-machine Versus Turing-machine Computation

This example is even more detailed than the above, because here the counter machine is specified to be a simulation in an EXCEL spread sheet. Where the "user" puts the parameters in the spreadsheet does matter.

We also observe that, while superficially similar, the core of the two algorithms is truly different: in this example the counter machine has to increment "m" times its parameter "n". (i.e. to add "m"=three to "n", increment "n" three times). In the Turing machine case the machine just had to fill in the first blank it came to, then find its way "home". It could have halted after filling in if we had specified this as acceptable. But the counter machine algorithm does not have this option.

Thus we conclude that: the algorithm is machine dependent.

(i) Number format: Positive integers (and 0) expressed in conventional decimal notation, one (unbounded) decimal integer per register. Zero is considered to be numeral 0 – the empty count, null, "blank B". The numerals themselves are simply abbreviations for unary counts within the registers:

"0" = B; "1" = |, "2" = | |, "3" = | | |

(iia) (Virtual, simulated) machine type: The machine to be used in the computation as a counter machine is equipped with only 3 registers (alternately: "Only three registers #0, #1, #2 will be used"). The instruction set will be the following three Minsky (1967) instructions:

INC ; INCrement contents of register r, proceed to next instruction in sequence: +1 → r, & +1 → state-machine instruction counter

DEC ;DECrement contents of register r, proceed to next instruction in sequence: -1 → r, & +1 → [ state-machine instruction counter

JZ ;Jump if contents of register r is Zero then go to instruction z else proceed to next instruction in sequence.

H ; HALT

(ib) Target (actual) machine: An EXCEL spreadsheet run on an Intel Pentium processor decodes and interprets the instructions and "runs" the (simulated) counter machine. The instructions – one per cell – are represented by symbol strings, for example, "I N C" or "i n c"; the instruction-operands are represented by decimal numeral symbols "3", "14", etc.

(iii) Head Location: No tape head is required. The instructions' operands – one per cell – are explicit names of the registers upon which the action will be taken and/or explicit jump-to addresses.

(iv) Location of the Program: The (virtual-) counter-machine program will be in its finite-state TABLE of instructions: In the EXCEL simulation this virtual program is located in the cells that represent the state-machine TABLE of instructions.

(iv) The program: A formal program listing is shown below.

High-level description:

Repeat until register #2 is 0:

While counting down the contents of register #2 to zero, count up the contents of register #1. The sum will accumulate in register #1.

Implementation description :

Implementation specification:

(a) Input format: The two arguments (m, n) of function "m+n" (e.g. "sum(m, n)") will be represented as integers expressed in conventional decimal notation, one (unbounded) decimal numeral per register. Unused registers will be considered to be blank/empty/of zero-count. Register #0 is reserved to hold the numeral “0” (blank, empty, zero-count). The following symbolism means "contents of register 5":

Example: integer 5 in register "3", = symbol "5" = | | | | |

(b) Initial location of arguments: The first argument "m" will be register #1, the second argument "n" in register #2.

Example: 2+3, =0, =m, =n

(c) Halt upon successful computation: : If the function m+n successfully assigns a value Σ to the arguments (m, n) that are represented initially on the tape, then the machine will eventually halt with the numeral Σ, represented in conventional decimal symbols, in a single register and otherwise-empty registers:

Example: m+n=∑, =0, =∑, =0

(d) Halt upon successful computation: register specified to hold output:In this case the machine will halt with the computation (sum Σ) in register #1:

Example: 3+2=5, =0, =5, =0

(e) Unsuccessful computation: If the function that is to be computed assigns no value to the arguments that are represented initially in the registers, then the machine either will never halt, or will halt in some nonstandard configuration:

Example: =3, =0, = 42, etc.

Implementation description:

• steps 1, 5: Test for n+0 and by implication 0+0: if register #2 is zero, then go to step 5 ’’done’’ else continue:
• steps 2, 3: Decrement register #2 and increment register #1; register #1 is accumulationg counts that will, upon halt, represent the sum.
• step 4: Unconditionally jump back to step 1 as follows: Test constant-register #0 for 0 (i.e. =0) and upon (always-)successful test jump back to step 1.

Formal description:

The program is written in “assembly code” mnemonics to be interpreted by an EXCEL program. Either upper- or lower-case may be used, but the spellings are mandatory. The format of how and where to put the code will be seen below and in the example:

Conventional assembly code listing:

"m+n":

1 JZ (2,5) ;=m: If =0 then instruction 5 else continue

2 DEC (2) ;Decrement count in register #2: -1 → 2

3 INC (1) ; =n or sum: Increment count in register #1: +1 → 1

4 JZ (0,1) ; IF =0 then jump to instruction 1 else continue.

5 HALT

The instruction "operation-codes" (assembly mnemonics) are to appear from left to right below their instruction numbers. The instruction "operands" (numerals) are to appear from left to right in separate cells below their mnemonics, as shown:

An example of the run of the program; time runs down the page: