Выдержка из книги
Кузнецов В.Е.
Представление в эвм неформальных процедур
Другими словами, всякий ли алгоритм представим в виде программы машины Поста. На первый взгляд уже сама бедность используемого алфавита П, X представляется препятствием для реализации в машине Поста сложных алгоритмов. Это значит, что любые исходные данные могут быть подходящим образом закодированы некоторой конфигурацией меток на ленте машины Поста. Точно также и результат работы машины Поста, т.е. конфигурацию меток, получаемую в случае результативной остановки машины, можно считать двоичным кодом некоторого содержательного результата.
