Е. Пост създава своята алгоритмична система през 1936 г., като въвежда въображаема машина, известна като машина на Пост.

Машината на Пост представлява механизъм, състоящ се от две части:

а) Лента, съдържаща еднакви квадратчета-клетки, подредени линейно. Лентата е безкрайна в двете посоки, което означава, че между клетките на лентата и целите числа (положителни, отрицателни и нула) може да се установи взаимно еднозначно съответствие, например:

Някои от клетките на лентата могат да бъдат отбелязани със символа „ * ", а други да не са отбелязани.

Броят на отбелязаните клетки може да се променя по време на функционирането на машината, но във всеки момент той е краен. Пример за едно състояние на лентата:

Считаме, че извън начертания участък няма отбелязани клетки, т. е. върху лентата има само пет отбелязани клетки.

б) четящо-записваща глава, която всеки момент се намира срещу някоя клетка на лентата, може да записва символа “*”, да го изтрива, да различава отбелязана и неотбелязана клетка и да се движи вляво и вдясно по лентата. Пример за моментно състояние на лентата на Пост:

                                         глава

Функциониране на машината на Пост

Работата на машината се ръководи от команди. Всяка команда има номер, определя какво действие да бъде изпълнено от главата и указва номера на следващата команда. В следващата таблица са описани възможните типове команди. С n е означен номерът на изпълняваната команда.

 

Команда	Изменение в положението на главата	Изменение в съдържанието на лентата	Номер на следваща команда
n. ←m	главата се премества срещу съседната отляво клетка		m
n. →m	главата се премества срещу съседната отдясно клетка		m
n. ↑m		изтрива се символът “*”, записан в клетката срещу главата	m
n. *m		записва се символът “*”, в клетката срещу главата	m
m n. ?           p			m - ако клетката, срещу която се намира главата, е празна р - в противен случай
n. СТОП			край на работата на машината

Пост определя формално понятието алгоритъм като съвкупност от команди от указаните типове. Функционирането на машината на Пост зависи от началното състояние на лентата и от алгоритъма, изразен чрез команди.

Да разгледаме примерния алгоритъм:

В следващата таблица се проследява работата на машината.

Машината на Пост може да извършва само описаните в таблицата действия. Възможно ли е да се опишат по-сложни алгоритми, например алгоритъм за събиране на две цели числа? Преди всичко възниква въпросът, как да се представят целите числа върху лентата. Най-простият начин е целите положителни числа да се представят чрез групи от съседни отбелязани клетки, а няколко числа да се отделят с една неотбелязана клетка. Поставяме си следната задача:

Да се състави алгоритъм чрез командите от следващата таблица, който по зададени две цели числа намира сумата им, като се използва вече условеното представяне.