Post machine (PM) is abstract, but tremendously simple model of computation. It is able to perform only the most elementary actions, so composing algorithms on Post machine is accessible even for pupils of primary school. On the other hand, Post machine is Turing tarpit, that means even implementation of trivial algorithms in it could be very hard, for the same reason. (PM memory model is also primitive, that is why the most part of interesting tasks is connected with data representation.) In this view, Post machine could be considered in some sense as esoteric programming language. Therefore, learning PM could be useful as effective way to improve algorithmic skills.
You can download PM emulator (includes program editor and interpreter) to make development on Post machine easier.
About PM
Post machine consists of:
- Two-way infinite sequence of spaces or boxes (unbounded in two directions tape divided into cells: each cell could be marked or unmarked at one moment — PM terminology).
- Worker (carriage), which is located opposite (“facing”) a particular cell at a time. In other words, carriage points the current cell of PM.
- Ordered list of commands (program), according to which worker changes the tape. It is also called instance of Post machine.
Distribution of marked and unmarked cells on the tape is called the state of the tape. Instance of PM should convert initial state in some concrete way. Result of working — state of the tape after machine terminating. Initially, infinitely-many cells are unmarked and the rest being marked.
Worker can move along the tape to neighbour cells and mark/unmark current cell. Commands contain instructions for it. Each of them must correspond to one of the following types:
| Type | C equivalent | Meaning |
| i. → j | a_i: p++;1 goto a_j; |
Move one cell to the right; then go to the j-th command. |
| i. ← j | a_i: p--; goto a_j; |
Move one cell to the left, ... |
| i. 1 j | a_i: *p = 1; goto a_j; |
Mark the current cell, ... |
| i. 0 j | a_i: *p = 0; goto a_j; |
Unmark the current cell, ... |
| i. ? j, k | a_i: if (*p) goto a_k; else goto a_j; |
If the current cell is empty, go to the j-th command, k-th otherwise. |
| i. ! | a_i: return 0; | Halt (finish work). |
| 1 defined char *p; | ||
In the beginning, worker performs the first command. On each step it is doing something on the tape and determines the next command to perform.
There are three possibilities after machine launch:
- It will halt working in a finite number of steps. This is successful finish.
- Machine will work indefinitely. Unless the contrary has been explicitly specified in the problem statement, this is considered as a failure.
- If worker attemps to mark already marked cell or vice versa — “erase” the empty one at some step, machine crashes. It always means your program is wrong.
Data representation
Natural number n can be written on the tape in unary notation, ie, simply as a sequence of n marked cells (n-block). When 0 is nessesary, n represents as n+1-block, then zero is written as one isolated mark.
Probably, the only proper way to encode text is Morse code. In this case, empty and marked cells correspond to the gaps and marks. Unfortunately, such representation is unsuitable for processing in PM. If you need to input some textual information, it is better to use the following method.
General approach
Enumerate all the objects that will be appear on the tape and “write” them as i-blocks, where i means object number, of cause. Determining the current item can be implemented through a chain of conditional operations:
1. ? m, 2 // empty cell — not the object
2. → 3
3. ? k1, 4 // k1 — start the first object processing
4. → 5
5. ? k2, 6 // k2 — start the second object processing
...
2n+1. ? kn, 2n+2 // kn — start the n-th object processing...
As can be seen, data representation in PM is really unconvenient. So (as it was mentioned above) it is more interesting to resolve “problems-on-tape”, e.g. problem of finding a single mark on the tape.
Programming tips
One of great issues to be faced anyone who will start programming on PM is lack of worker’s memory. This leads to the impossibility of re-use typical structures and need of writing any temporary data on the tape. You should always remember about this during the development on PM.
The basic method of programming on Post machine is recursion. In fact, any how a complex algorithm contains a recursive part. In solving the problem the first thing which should be made is extraction of invariant of the loop.
There are not too many tricky (and executable!) problems on PM, so one of “sport” directions is reducing number of lines in solution of specific task. For example, you can try to implement multiplication in 50 lines or less (it is possible).
Glossary
Caret, carriage, machine, head, pointer — the worker.
Empty cell, space, nil — unmarked cell.
Mark, label, box, unit — marked cell.
Line (of program), instruction, direction — command.
Current cell — the cell which the worker is being in at the moment.
Current line — command which is performing by the worker at the moment.
Block (n-block) — n marked cells in a row.
Machine, Post machine, program — PM instance.