Algorithm Examples - Footnotes

Footnotes

• Footnote: Coding instructions for the finite state machine (FSM):

Models of machine computation such as the Turing machine and counter-machine are considered to be, in a sense, real machines. That is, their finite cousins have to be buildable if someone were so inclined. In the literature, examples of coding for the models usually stop at the tabular level (tables of 4- or 5-tuples) for Turing machines and at the mnemonic level for the various Register machine models

Example for the Post-Turing machine model: { L, R, E, P, J0 xxx; J1 xxx; H }.

In his paper (1936) Turing went a level further and encoded his tabular 5-tuples into a string of numbers chosen from 1-7. But this encoding was for the instructions of his "universal machine" to be put on the tape. He did not go into much detail with regards to encoding instructions for the finite state machine.

The standard methods of bottom-level encoding are of only a few types and always use numbers, because symbols other than numbers can be easily translated into number-equivalents (cf Boolos-Burgess-Jeffrey):

• Unary, e.g. "3" = | | |, or more likely if "0" = |, "3" = | | | |
• One of n: where each column is similar to "a wire" with a condition of "1" or "0 = empty". A number is thus represented as an ordinal.

• polynomial: base-n, e.g. binary, decimal

binary: n₀*2₀ + n₀*21 + n₂*22 + ... + n_m*2m

decimal: n₀*10₀ + n₀*101 + n₂*102 + ... + n_m*10m

• Gödel numbering expressed in, probably, binary or decimal

The solution will depend on the nature of the "memory" of the FSM. If it is built from a typical binary Random access memory then the instruction "address" (number) will have to be encoded as binary. The instruction code can be chosen from whatever method is most easy to decode and "fits in the width of the memory".

This is not a trivial problem, and appears in the work of authors who are encoding for purposes of comparing algorithms . What they tend to do is use e.g. two consecutive 8-bit memory "cells" for every instruction (or e.g. 2 x 16 bit). Thus they might encode an instruction set as follows:

FSM encoding for up to 128 registers and 256 instructions with an 8-bit random-access memory with two consecutive 8-bit bytes:

*0hhhhhhh: the identifier-number/location/identifier of register h expressed in binary (0 through 127). Example: register #5 = 00000101

*xxxxxxxx: the jump-to address expressed in binary (0 through 255)

• INC h = 00000001, 0hhhhhhh
• DEC h = 00000010, 0hhhhhhh
• JZ h,x = 1hhhhhhh, xxxxxxxx
• HALT = 111----- are both expressed in binary

Thus the first byte always specifies the instruction type. And this type specifies where the 7-bit register number hhhhhhh and the jump-to address will be. But such coding complicates the finite state machine -- it must be smart enough to know (i) interleave and (ii) that if 011hhhhh occurs then the next instruction will be a jump-to address. And if a mistake is made, the machine can begin to "execute" operands instead of instructions.