Examples

There are some realisations of the simpliest operations and algorithms with numbers on Post Machine model below.

Common assertions

The examples are given in this syntax of Post Machine. (However, the interpreter supports version with different conditional operator too.)

Any input numbers: summands, multipliers, indexes should be positive integers. It isn’t general constrain for Post Machine, but for all the following solutions.

In PM-model computational complexity of the algorithm could be formalized as number of commands to perform required to obtain the result as function S from the input size or values (that often equals in Post Machine).

Most S-functions are determined up to the Θ-notation (see definition; also w:Big Theta). As usual in O-notations, form S(x,y)=Θ(f(x,y)) means S(x,y)∈Θ(f(x,y)).

Problem statement consists of two tape states: initial and terminational. Zeros and ones signify empty and marked cells; down arrow points initial and (not necessary) final carriage position. Under each block of units is written its length.

Addition

 0. !
 1. 0
 2. →
 3. ? 4, 2
 4. 1 0

S(n,m)=2n+3 — doesn't depend on the second summand.

Summation

 0. !      summation
 1. 0
 2. →
 3. ? 4, 2
 4. 1
 5. →
 6. ? 0, 7
 7. ←
 8. ? 9, 7
 9. → 1

S(n₁,n₂,...,n_k)=Θ(kN), where N=∑n_j

Subtraction

0. !       subtraction
1. →
2. ? 3, 1
3. ←
4. 0 
5. ←
6. ? 14, 7
7. →
8. ? 7, 9
9. 0
10. →
11. ? 0, 12
12. ←
13. ? 12, 4
14. → 
15. ? 14, 16
16. 0 0

S(n,m)=Θ(min(n,m)²)

Multiplication

 0. !          multiplication
 1. 0          .loop: make row
 2. →
 3. ? 29, 4    .end loop
 4. →
 5. ? 6, 4
 6. →
 7. ? 8, 4
 8. ←
 9. ←
10. 0          ..loop: copy m-factor
11. →
12. ? 13, 11
13. →
14. ? 15, 13
15. 1
16. ←
17. ? 18, 16
18. ←
19. ? 20, 18
20. 1
21. ←
22. ? 23, 10   ..end loop
23. ← 
24. ? 25, 23
25. ←
26. ? 27, 23
27. →
28. → 1
29. →          summation of "copies" of the m-block
30. 0
31. →
32. ? 33, 31
33. 1
34. →
35. ? 0, 36    exit
36. ←
37. ? 29, 36

S(n,m)=Θ(nm(n+m))

 0. !
 1. 0          //main loop
 2. →
 3. ? 4, 2
 4. →
 5. 0          //loop by second multiplier
 6. →
 7. ? 8, 6
 8. →
 9. ? 10, 8
10. 1
11. ←
12. ? 13, 11
13. ←
14. ? 15, 13
15. 1
16. →
17. ? 18, 5
18. ←
19. ? 20 18
20. ←
21. ? 25, 22
22. ←
23. ? 24, 22
24. → 1
25. →
26. →          //erase second multiple
27. ? 0, 28
28. 0 26

S(n,m)=Θ(n²m²)

Both algorithms are based on simple idea that multiplication is shortcut summation. The first one takes 9 commands more than the second, but computes result faster.

Division

 0. !
 1. 0          .loop: subtract divisor from dividend
 2. →
 3. ? 4, 2
 4. →
 5. ? 25, 6
 6. →
 7. ? 8, 6
 8. ←
 9. 0
10. ←
11. ? 12, 10
12. ←
13. ? 14, 12
14. 1
15. →
16. ? 17, 1    .end
17. ←          / +1 to the result
18. ? 19, 17
19. ←
20. ? 21, 19
21. 1
22. →
23. ? 24, 22
24. → 1        /
25. ←          dirive the remainder
26. ← 
27. ? 29, 28
28. 0 26
29. ←          place the caret between
30. ? 0, 29

How does it work? The divisor is substracted from the dividend as long as possible. (Result is incremented for each such step.) When the dividend “runs out”, it appears, that the divisor-block divided into remainder and the complement by the empty cell. There remains to erase units of the divisor up to the space and place pointer between quotient and reminder.

S(n,m)=Θ(n(n+m))

Output the n^th Fibonacci number

 0. !
 1. ←           init F_1 = 1
 2. ←
 3. 1           .
 4. →
 5. ? 4, 6
 6. 0
 7. →
 8. ? 36, 9
 9. ←
10. ? 9, 11
11. 0           .loop: copying F_i
12. ←
13. ? 14, 12
14. ←
15. ? 16, 14
16. ←
17. ? 18, 16
18. 1
19. →
20. ? 21, 19
21. →
22. ? 23, 21
23. →
24. ? 29, 25
25. →
26. ? 27, 25
27. 1
28. ← 11        .end 
29. 1           merging F_i and F_i-1
30. ←
31. 1
32. →
33. ? 34, 32
34. ←
35. 0 4         .
36. ←           erase F_i-1
37. ? 36, 38
38. ←
39. ? 40, 38
40. ←
41. ? 0, 42
42. 0 40

S(n)=Θ(F_n+1F_n+2)=Θ(ϕ²ⁿ⁻¹), where  ϕ≈1.62  is golden ratio.

Notes

Constants hidden in Θ-notations are quite small (vary from 0.9 to 5).

Most examples are written by Andrey Astrelin (big respect for him :-)