User:Wvbailey/Algorithm definition: example
The following example is a supplement to the article algorithm.
The word "algorithm" has no agreed-upon definition. The following example is meant to show wherein lie the difficulties.
The "computer"
> Whenever we encounter "an algorithm" we encounter a list of instructions with, more often than not, an implied appeal to an active agent. This "agent" we will call "the computer".
We quickly discover when we consider a machine-as-agent is that there is a second "computer" involved -- "the user". It is naive to think that the computer is the sole active agent in the picture. As we will see below the algorithm must include this "user" in its definition.
The "computer" can be either a man with paper and pencil, or an automatic machine. Knuth suggests that:
- "An algorithm must be seen to be believed. The best way to learn what an algorithm is all about is to try it. The reader should always take pencil and paper and work through an example..."(Knuth Vol. 1, p. 4)
Post-Turing machine modified with a Minsky counter
The Post-Turing machine model of a computation is about as primitive a computational machine that can be imagined, and yet, it is Turing equivalent -- it can (hypothetically) compute anything computable. Wang (1954, 1957) shows how to reduce the Post-Turing model even further (to only 3 or 4 instructions), but what he ends up with is so hard to use that most commentators (e.g. Davis), and including Wang himself, adopt a model with a few more instructions.
Post-Turing machine model: summary
Head moves, prints on or erases a tape: A tape of indefinite length is divided into squares. The tape passes through a "head" that moves the tape one square LEFT L or RIGHT R. When the head scans a square it can PRINT P a single symbol, perhaps a "tally mark", or overprint a mark already there. Or the head can ERASE E a mark or "over-erase" a blank square.
The head observes the scanned square: Additionally the "head" read/observes the scanned square and provides the symbol -- "0" = blank, and "1" = mark -- to the a list of instructions. (a state machine
The machine obeys a list (string) of instructions: every instruction in the list/string is identified with a unique number (a positive integer), usually but not necessarily, listed in consecutive order. This is called the instruction's ADDRESS.
Each particular address has only one of 9 instructions is associated with it: The 9 instructions are:
- { { }, R, L, E, P, J0, J1, J, H }
{ } stands for "nop" and occurs if an instruction is blank. H stands for halt. For example instruction #6 has LEFT L associated with it
- 6 L
The "program counter": An up-counter produces the address of the next instruction for the machine to obey. (This is the correlative of the "state register" of a Turing machine). The counter "counts up" to produce the next address until it encounters a "jump-to" instruction. Unless the up-counter is commanded otherwise, the instructions occur in numerical sequence, i.e.
- 6 L
- 7 E
- 8 L
Jump-to instructions may the program counter out of numerical sequence: A successful 'jump-to' instruction "jams" the program counter with a "jump-to" address. There are two types of jump-to instructions: "conditional" jump-to and an "unconditional" jump-to:
- (1a) JUMP-IF-scanned-symbol-is-1-to-instruction-#xxx J1,xxx
- (1b) JUMP-IF-scanned-symbol-is-1-0/blank-to-instruction-#xxx J0,xxx
- (2) JUMP-to-instruction-#xxx J,xxx.
In the case of the conditional instructions the program-counter AND the scanned symbol either jam/jumps the program-counter out of sequence to the specified instruction #xxx or allows the program-counter to continue onward in sequence. In the case of the unconditional jumpthe machine has no choice but to jump out of sequence to the specified instruction.
- 6 L
- 7 E
- 8 L
- 9 J0 22 ;if the tape is blank,
The machine === Minsky machine model: summary The Minsky machine -- what Minsky called a program machine -- is just as reduced, and with 4 to 5 registers, it too is "Turing equivalent". Instead of a single tape of infinite length, it has a small number of "registers" -- up/down counters.
Modify the model slightly with a