Машина Поста

Пост утверждает, что всякая вычислимая функция вычислима по Посту, т. е. с помощью машины Поста.

Как бы это доказать? Не знаю даже как подступиться. Достаточно ли доказать, что можно сложить, вычесть, умножить и разделить, а потом сказать, что всякие там функции можно разложить в ряд? Или есть какие-то еще загвоздки? Кстати, как разделить? Что делать с дробями?

Подписаться на блог
Отправить
Дальше
Мои книги