Algorithm Examples - Footnotes


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.
number 1st 2nd 3rd 4th 5th ... n+1th
0 1
1 1
2 1
3 1
... 1 ....
n 1
  • polynomial: base-n, e.g. binary, decimal
binary: n0*20 + n0*21 + n2*22 + ... + nm*2m
decimal: n0*100 + n0*101 + n2*102 + ... + nm*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.

Read more about this topic:  Algorithm Examples

Other articles related to "footnote, footnotes":

Jonathan Strange & Mr Norrell - Style
... on the first page of the novel, but only in a footnote ... He reappears in other footnotes throughout the opening but does not appear as a character in the text proper until a quarter of the way through the novel ... Clarke's style extends to the novel's 185 footnotes, which document a meticulous invented history of English magic ...
Ciaphas Cain - Character
... Vail must also add occasional footnotes to some of his recollections to point out that Cain has just glossed over something another man might take pride in ... Vail's footnotes in the second novel indicated Cain was probably one of the finest swordsmen in his region of the galaxy ... Vail's footnotes indicate that, despite her research into the subject, she could find no official documentation on where he was born or what his childhood was like ...
Princeton Footnotes
... The Princeton Footnotes are a traditional all-male a cappella group from Princeton University in Princeton, NJ ... The Footnotes are a student-run, semi-professional performance group ... The Footnotes came in third in the National Collegiate A Cappella Championship Semi-Final in 2000 ...