From Wikipedia, the free encyclopedia

The following example is a supplement to the article algorithm.

[edit] The problem -- no agreed-to definition

The word "algorithm" has no agreed-upon definition. The following example is meant to show wherein lie the difficulties. Our example will use "multiply" as our example "function" to be computed using "an algorithm".

[edit] The "computer"

The multiply program is to the upper right. It performs the multiplication c = a x b. The input "switches" to input parameters a and b are on the left and the output c is to their right. The tape is in the middle.

> 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)

[edit] Post-Turing machine modified with one Minsky counter/register

The Post-Turing machine model of a computation is about as primitive a computational machine that we can define that is Turing equivalent -- it can (hypothetically) compute anything computable.

The Minsky machine model is equally primitive and it too can be Turing equivalent, given four or five "registers". Both models share a similar type of "sub-machine" that provides the instructions necessary to do the computations.

To (i) ease our suffering through the multiplier's sequence of Post-Turing instructions, and (ii) to provide a output location, we will add a single Minsky register to our Post-Turing machine. The Post-Turing machine will handle the input and the computation while the Minsky register will present the output as a number (rather than an arcane string of tally marks).

The following instructions are used by the machine:

[edit] Post-Turing machine model: summary

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, have adopted a model with a few more instructions (i.e E, J0, J).

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 is in position on a square it can PRINT P a single symbol, perhaps a star "*" or a "tally mark" (but only one symbol per machine), or overprint a mark already there. Or the head can ERASE E a mark or "over-erase" a blank square.

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.

The "program counter" begins with a count of #1 (#0 in some designs) and increments from there: The "program counter" is an up-counter that can be "jammed" with an arbitrary address (i.e. integer) anywhere within its allowable-but-very finite address "space" (extent).

We must "initialize" our machine's program counter to the first-most instruction in an instruction sequence/program: But a program need not start at #1. As we will see, we need a way to inform our machine of the instruction number to start its computation.

For example: "multiply" starts at instruction #2

For example: "tape-clean" starts at instruction #22.

The "program counter" steps the machine through its instructions: In next-integer-sequence, an up-counter holds the current instruction while the instruction executes, then 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" in sequence (succession) to produce the next address i.e.

The head observes the scanned square: The "head" can read/observe the scanned square and provides the symbol -- "0" = blank, and "1" = mark -- to the program counter while it is on/over the square. This information is used by the program counter to test the square's "condition" -- as marked or blank. We assume that the tape is motionless and not being printed or erased when scanned while testing for a JUMP.

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, else next instruction in sequence.

(1b) JUMP-IF-scanned-symbol-is-1-0/blank-to-instruction-#xxx J0,xxx, else next instruction in sequence.

(2) JUMP-to-instruction-#xxx J,xxx.

In the case of the conditional "jumps" 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.

[edit] 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.

Like the Post-Turing model our machine will execute its instructions in sequence unless a successful conditional jump-to sends it out of sequence.

A Minsky register is a counter: It is considered to be of infinite extent. It can be commanded to COUNT UP U (increment), or COUNT DOWN "a" AND JUMP IF ZERO or to jam itself with ZERO Z.

We will atomize the Minsky COUNT DOWN "a" AND JUMP IF ZERO instruction into a two-instruction sequence "Decrement register a" and "jump-if-zero to xxx":

D a

JZ,xxx

Unlike a true Minsky machine we will equip our model with only 1 counter (a true Minsky machine requires at least two). As it turns out we will not need this instruction, nor will we need the D instruction.

D

A Minsky jump occurs if the instruction is JZ,xxx and the specified counter contains 0: We will use only one counter so we don't need to specify it:

jump-if-counter-is-0-to-xxx, JZ,xxx

[edit] Control Panel

How do we input numbers into our machine?

Input-run switch: We equip our machine with a toggle switch, that, when in position "run" will "execute" the program starting wherever the program counter is set. If it is in the "input" position we as "users" can "play computer" manually enter data as if we were a program. To do this we need the following push-button switches.

Push-button switches:

L

R

P

E

Z

J

jump-to address