1. На информационной ленте машины Поста расположен массив из N меток. Каретка находится под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы?
1 → 2
2 ↕ 3
3 → 4
4 ? 5,2
5 ← 6
6 v 7
7 !
Команда 1 → 2 перемещает каретку вправо. Команда 2 ? 1,3 проверяет, есть ли метка под кареткой. Так как массив меток не указан, предположим, что метка отсутствует, и выполнится переход к команде 3. Команда 3 → 4 перемещает каретку вправо. Команда 4 ? 5, 3 снова проверяет наличие метки под кареткой. Так как предыдущая проверка не выявила метку, предположим, что ее все равно нет, и выполнится переход к команде 3 (цикл). Команда 3 → 4 снова перемещает каретку вправо. Команда 4 ? 5, 3 снова проверяет наличие метки. Так как предыдущая проверка также не выявила метку, выполнится переход к команде 5. Команда 5 v 6 перемещает каретку влево (возврат к началу цикла). Процесс повторяется с команды 2. Таким образом, программа будет бесконечно циклически выполнять команды 1-5, не изменяя состояния ленты.
2. На информационной ленте на некотором расстоянии справа от каретки, стоящей под пустой клеткой, находится непрерывный массив меток. Требуется присоединить к правому концу массива одну метку.
Команда 1 → 2 перемещает каретку вправо. Команда 2 ? 1,3 проверяет наличие метки под кареткой. Поскольку предполагается, что справа от каретки есть непрерывный массив меток, то метка будет обнаружена, и выполнится переход к команде 3. Команда 3 → 4 перемещает каретку вправо. Команда 4 ? 5, 3 проверяет наличие метки под кареткой. Опять же, предполагается, что метка обнаружена, и выполнится переход к команде 3 (цикл). Команда 3 → 4 снова перемещает каретку вправо. Команда 4 ? 5, 3 снова проверяет наличие метки. Так как предыдущая проверка также обнаружила метку, выполнится переход к команде 3 (цикл). Процесс будет бесконечно циклически выполнять команды 1-4, добавляя метку к правому концу массива при каждой итерации цикла. Таким образом, после выполнения этой программы будет добавлена одна метка к правому концу массива меток.
3. На ленте расположен массив из 2n - 1 меток. Составить программу отыскания средней метки и стирания ее.
Для нахождения средней метки и её стирания на ленте с массивом из 2n - 1 меток можно использовать следующую программу:
1 → 2 2 → 3 3 → 4 4 → 5 5 ? 6, 7 6 → 7 7 ← 8 8 ? 9, 10 9 ← 10 10 ! 11 → 12 12 ? 13 → 14 14 ← 15 15 ?
Рассмотрим действия программы:
Команда 1 → 2 перемещает каретку вправо. Команда 2 → 3 снова перемещает каретку вправо. Команда 3 → 4 продолжает перемещение каретки вправо. Команда 4 → 5 продолжает перемещение каретки вправо. Команда 5 ? 6, 7 проверяет наличие метки под кареткой. Если метка есть, то выполнится переход к команде 6, иначе к команде 7. Команда 6 → 7 сдвигает каретку вправо, пройдя метку. Команда 7 ← 8 перемещает каретку влево. Команда 8 ? 9, 10 проверяет наличие метки под кареткой. Если метка есть, то выполнится переход к команде 9, иначе к команде 10. Команда 9 ← 10 сдвигает каретку влево, пройдя метку. Команда 10 ! завершает программу. После выполнения этой программы каретка остановится на средней метке, и она будет стёрта с ленты.
4. На ленте расположен массив из 2n меток. Составить программу, по которой машина раздвинет на расстояние в одну клетку две половины данного массива.
Для раздвигания двух половин массива меток на расстояние в одну клетку можно использовать следующую программу:
1 → 2 2 → 3 3 → 4 4 ? 5, 6 5 → 6 6 ← 7 7 ? 8, 9 8 ← 9 9 !
Команда 1 → 2 перемещает каретку вправо. Команда 2 → 3 снова перемещает каретку вправо. Команда 3 → 4 продолжает перемещение каретки вправо. Команда 4 ? 5, 6 проверяет наличие метки под кареткой. Если метка есть, то выполнится переход к команде 5, иначе к команде 6. Команда 5 → 6 сдвигает каретку вправо, пройдя метку. Команда 6 ← 7 перемещает каретку влево. Команда 7 ? 8, 9 проверяет наличие метки под кареткой. Если метка есть, то выполнится переход к команде 8, иначе к команде 9. Команда 8 ← 9 сдвигает каретку влево, пройдя метку. Команда 9 ! завершает программу.