Состояния машины и ее ограничения
У машины Тьюринга, реализующей функцию Y=[X÷2] будет 2 элемента:
- указатель
- лента
Кроме того, машина будет иметь 4 состояния системы:
Ход вправо нечетный раз и обнуляем символ
Ход вправо четный раз, снова обнуляем символ и запоминаем единицу
Ход влево в поиске последнего значащего символа (1 или ограничитель ленты 2)
Возвращение на 1 позицию назад для вставки значащего символа
Ограничения, вводимые для данной программы:
Пользователь может ввести только целое число
Число должно быть больше 1 и меньше 100
При введении нечетного числа, округление идет в меньшую сторону(например, для числа 5, программа выведет ответ [11])
Алгоритм реализации
Пользователь вводит любое число Х, ограниченное промежутком [2;99]
Встроенная функция переводит это число в массив, где количество элементов равняется Х+2, заполняет массив единицами и ограничивает его специальным элементом, указывающим на начало и конец ленты, 2.
Для того, чтобы выполнить поставленную задачу, нам необходимо обнулить каждую нечетную по счету единицу, а каждую четную единицу перевести в начало массива.
Работа машины Тьюринга начинается с первого символа, т.е. с нечетного хода. Мы обнуляем единицу и переходим к следующей ячейке.
Далее следует четный ход. Ячейка обнуляется, но его значение запоминается для переноса.
Двигаемся влево до тех пор, пока не обнаружим последний значащий символ. В нашем случае это может быть либо ограничивающий символ(2), либо последняя перенесенная единица. Наткнулись на ячейку со значением.
Двигаемся на одну клетку вправо и вставляем единицу.
После ход начинается уже с четного, но в ячейке будет уже обнуленное значение, поэтому ячейку мы пропускаем.
Переходим снова в нечетному ходу. И так двигаемся до тех пор, пока не встретим последний ограничивающий символ 2.
Выводим полученный результат.
Промоделируем работу машины Тьюринга для значения 5.
Номер итерации |
Лента |
0 |
#-1-1 1 1 1 # |
1 |
# 0-1-1 1 1 # |
2 |
#-0-0 1 1 1 # |
3 |
-#-0 0 1 1 1 # |
4 |
1-0-0 1 1 1 # |
5 |
1 0-0-1 1 1 # |
6 |
1 0 0-1-1 1 # |
7 |
1 0 0 0-1-1 # |
8 |
1 0 0-0-0 1 # |
9 |
1 0-0-0 0 1 # |
10 |
1-0-0 0 0 1 # |
11 |
1-0-0 0 0 1 # |
12 |
1-0-0 0 0 1 # |
13 |
1 1-0-0 0 1 # |
14 |
1 1 0-0-0 1 # |
15 |
1 1 0 0-0-1 # |
16 |
1 1 0 0 0-1-# |
17 |
1 1 0 0 0 0-#- |
18 |
1 1 0 0 0 0 0 |
Таблица составляется из инструкций для МТ в виде структур
{новый_символ; новое_состояние; смещение_головки}
Таблица (направо - состояния, вниз - текущие значения в ячейке)
'!!! ' означает, что данный алгоритм исключает такое стечение обстоятельств, но тем не менее, надо это предусмотреть и сделать на этот случай инструкцию с аварийным остановом и выводом сообщения о нарушении в работе машины
|
1 |
2 |
3 |
4 |
0 |
0;1;+1 0;2;+1 |
0;3;-1 1;1;+1 |
0;5;-1 |
|
1 |
0;2;+1 0;3;-1 |
!!! |
!!! |
!!! |
# |
0;5;-1 0;5;-1 |
1;4;+1 !!! |
0 |
остановка; 0 |