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
The head moves the tape, prints on or erases the scanned square: 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, each with a distinct ADDRESS: 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 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
| Instruction # | Instruction | Next Instruction # | |
| 7 | L | 8 | Move tape LEFT |
The "program counter" steps the machine through its instructions: In next-integer-sequence, 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). Until it encounters a "jump-to" instruction the counter "counts up" to produce the next address i.e.
| Instruction # | Instruction | Next Instruction # | |
| 7 | L | 8 | Move tape LEFT |
| 8 | E | 9 | ERASE tape (print 0) |
| 9 | L | 10 | move tape LEFT |
Jump-to instructions may force 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 agreement of instruction AND scanned symbol jam/jumps the program-counter out of sequence to the specified instruction #xxx; otherwise, the program-counter continues onward in sequence. In the case of the unconditional jump J,xxx the instruction forces the program count out of sequence and to the specified instruction.
| Instruction # | Instruction | scanned square | Next Instruction # | |
| 7 | L | 0 or 1 | 8 | Move tape LEFT |
| 8 | E | 0 or 1 | 9 | ERASE tape (print 0) |
| 9 | L | 0 or 1 | 10 | move tape LEFT |
| 10 | J0, 22 | 0 | 22 | scanned square = 0 so jump to 22 |
| 10 | J0, 22 | 1 | 11 | scanned square = 1, jump fails |
Minsky machine model: summary
The Minsky machine -- what Minsky called a program machine -- is just as reduced as the Post-Turing machine, and if equipped 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 of infinite extent.