Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д.
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:
1 -> 2
2 ? 1;3
3 <- 4="" br="">4 V 5
5 !
А процесс выполнения может быть таким:
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д.
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:
1 -> 2
2 ? 1;3
3 <- 4="" br="">4 V 5
5 !
А процесс выполнения может быть таким:
Изображения, использованные в статье Машина Поста. Прибавление единицы к числу
Комментариев нет:
Отправить комментарий