A Post machine is an abstract computing machine consisting of a two-way unbounded tape divided into boxes, each of which is either blank or marked, together with a finite numbered program. Its elementary instructions mark or erase the current box, move one box left or right, transfer control conditionally according to whether the current box is marked, or halt.
Post (1936) introduced the model as a particularly simple formulation of a general combinatory process. Post machines and Turing machines compute the same class of computable functions, so the model is one of the equivalent formalisms supporting the Church-Turing thesis (Davis 1982).
