Post’s Machine (Little Mathematics Library) | V. A. Uspensky

This booklet is intended first of all for school children. The first two chapters are comprehensible even for junior schoolchildren. The book deals with a certain “toy” (“abstract” in scientific terms) computing machine – the so called Post machine – on which calculations involve many important features inherent in the computations on real electronic computers. By means of the simplest examples the students are taught the fundamentals of programming for the Post machine, and the machine, though extremely simple, is found to possess quite high potentialities.The reader is not expected to have any knowledge of mathematics beyond the primary school curriculum.

The book was translated from the Russian by R. Alavina and was first published by Mir in 1983. Contents of the book are as under:

1. How the Post Machine Works 9
Sec. 1.1. “An Outward Appearance” of the Post Machine
Sec. 1.2. The Program for the Post Machine
Sec. 1.3. The Operation of the Post Machine
Sec. 1.4. Examples of Performing Programs
Sec. 1.5. Methodological Notes
2. Addition of Unity on the Post Machine 23
Sec. 2.1. Recording umbers on the Post Machine and the Statement of the Problem on Addition of Unity
Sec. 2.2. Addition of Unity in the Simplest Case
Sec. 2.3. Addition of Unity in More Complicated Cases
Sec. 2.4. Addition of Unity in Yet More Complicated Case
Sec. 2.5. Addition of Unity in the Most General Case
3. Analysis and Synthesis of Programs for the Post Machine 39
Sec. 3.1. Diagrams and Block Diagrams
Sec. 3.2. Analysis of the Program of Adding Unity
Sec. 3.3. Again on the Problem on Addition of Unity
Sec. 3.4. Addition of Numbers in Simple Cases
Sec. 3.5. Addition of Numbers in More Complicated Cases
4. The Post Machine Potentialities 60
Sec. 4.1. On the Problem of Addition of Numbers at Arbitrary Distances
Sec. 4.2. Post’s Proposal
Sec. 4.3. The Post Machine and Algorithms
Sec. 4.4. Additional Comments on Post’s Hypothesis (Post’s Thesis and Post’s Principle)
Sec. 4.5. The Post Machine and Electronic Computers

Supplement 82

Finite Combinatory Processes Formulation 1 84