Published on in “Science”, language — Russian. 7 pages.
Машина Поста — это абстрактная (т.е. не существующая в арсенале действующей техники), но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия. Тем не менее на машине Поста можно запрограммировать — в известном смысле — любые алгоритмы. More
