Question

Помогите, пожалуйста! На ленте машины Поста расположен массив из 2n ячеек. Составить программу, по которой машина Поста раздвинет на расстояние в одну ячейку две половины данного массива.

Answer 1

Идея возможного решения: по очереди будем оттаскивать в сторону по одной метке с каждой стороны. В итоге получатся две половины, разделенные двумя пустыми ячейками. Чтобы получить то, что надо, нужно сдвинуть одну половину в направлении другой.

Поясняющая картинка и программа (обозначения такие же, как в программе Полякова) в приложенных картинках,

Answer 2

Конечно, помогу! Для того чтобы машина Поста раздвинула на расстояние в одну ячейку две половины массива из 2n ячеек, нужно использовать следующую программу машины Поста:

1. Переместиться в начало массива.
2. Отметить начало первой половины массива.
3. Переместиться в начало второй половины массива.
4. Отметить начало второй половины массива.
5. Переместиться в конец первой половины массива.
6. Пока текущая ячейка не пуста (не содержит символа), переместиться вправо.
7. Переместиться в начало первой половины массива.
8. Пока текущая ячейка не пуста (не содержит символа), переместиться вправо.
9. Переместиться в начало второй половины массива.
10. Пока текущая ячейка не пуста (не содержит символа), переместиться вправо.
11. Отметить начало первой половины массива.
12. Переместиться в начало второй половины массива.
13. Отметить начало второй половины массива.
14. Переместиться в конец первой половины массива.

Теперь давайте представим символ "#" как маркер начала или конца половины массива. Допустим, у нас есть массив из 2n ячеек, где a, b, c и d - произвольные символы, а "#" - маркер начала или конца половины массива:

cssCopy code
a b c d # a b c d #

Программа машины Поста будет выглядеть следующим образом (допустим, начальное состояние машины Поста находится на первой ячейке массива):

markdownCopy code
1. > > * *
2. [ ]
3. > > > *
4. [ ]
5. < < < *
6. > > * *
7. < < < *
8. > > * *
9. < < < *
10. [ ]
11. > > * *
12. < < < *
13. [ ]
14. < < < *

Где:

• > - перейти в следующую ячейку вправо
• < - перейти в следующую ячейку влево
• [ ] - проверить текущую ячейку на пустоту
• * - записать в текущую ячейку символ "*"

Эта программа переместит две половины массива на расстояние в одну ячейку. Необходимо убедиться, что символ "*" не встречается в исходном массиве, чтобы избежать конфликтов при выполнении программы.