Машина Тьюринга: умножить число на 2, если каретка находится над крайней левой цифрой числа / Теория автоматов

q0 -конечное состояние
P - пустой символ
L - в лево
R - в право
N - стоим
q1 - начальное состояние

1. бежим в конец числа:
q1 n->q1 nR
q1 P->q2 PL
где n от 0 до 9

2. числа от 0 до 4 можно просто умножить, без запоминания 1
q2 - состояние, когда нет единицы для запоминания

q2 0->q2 0L
q2 1->q2 2L
q2 2->q2 4L
q2 3->q2 6L
q2 4->q2 8L

3. если цифры от 5 до 9, то нужно запомнить 1 и прибавить на следующем шаге
q2 5->q3 0L
q2 6->q3 2L
q2 7->q3 4L
q2 8->q3 6L
q2 9->q3 8L

q3-состояние, когда мы умножаем на 2 и прибавляем 1 к результату

3. если цифры от 0 до 4, то после "избавления" от 1 ничего запоминать не нужно
q3 0->q2 1L
q3 1->q2 3L
q3 2->q2 5L
q3 3->q2 7L
q3 4->q2 9L

4. если цифры от 5 до 9, то после "избавления" от 1, мы снова ее запоминаем
q3 5->q3 1L
q3 6->q3 3L
q3 7->q3 5L
q3 8->q3 7L
q3 9->q3 9L

5. заканчиваем программу, когда встречаем пустой символ
q2 P->q0 N
q3 P->q0 1N
если мы все еще помним 1, а уже число закончилось, то на пустой клетке пишем 1.

Д) Деление

Решение
--------

Пусть исходные данные такие:
1. Число X в унарной системе = X палочек записанных в соседних клетках ленты
2. Лента бесконечная
3. Справа и слева от числа пустые клетки
4. Число 0 (ноль) = пустая лента
8. Обозначение состояний: S0,S1,S2 и т.д.
5. Начальное состояние = S1
6. Окончание работы - переход в состояние S0
7. Начальное положение машины - правая палочка для N>0 или неважно для N=0
8. Конечное положение машины - не важно
9. Структура машины состоит из записей следующего вида:
Sx,Nx -> Sy,Ny,D
где:
Sx - состояние до выполнения шага (S1,S2,S3... и т.д. кроме S0),
Sy - состояния после выполнения шага (S0,S1,S2,S3... и т.д.),
Nx - значение клетки до выполнения шага (1 - палочка, 0 - пусто)
Ny - значение клетки после выполнения шага (1 - палочка, 0 - пусто)
D - направление передвижения машины после выполнения шага:
(R - вправо, L - влево, N - остаться на месте)

Например:
S1,1 -> S2,1,L
означает:
если состояние S1 и палочка, то переходим в состояние S2, оставляем палочку, сдвигаемся влево

Итак,

Задача1: X mod 2
-----------------
Идея: "Двигаться справа налево, стирать справа по две палочки до тех пор,
пока не останется одна единственная палочка (для нечетного числа)
или пустая лента (для четного числа и нуля)"

S1,0 -> S0,0,N;ЕСЛИ пустая клетка, остаться на месте, завершение работы, результат = 0
S1,1 -> S2,1,L;ИНАЧЕ первая палочка, оставим ее и проверим следующую клетку слева
S2,1 -> S3,0,R;ЕСЛИ вторая палочка, стираем ее и передвигаемся вправо чтобы стереть первую палочку
S3,1 -> S4,0,L; стираем первую палочку и возвращаемся влево на стертую ранее палочку
S2,0 -> S0,0,N;ИНАЧЕ все палочки закончились, остаться на месте, завершение работы, результат = 1
S4,0 -> S1,0,L;Стерли две палочки, сдвигаемся влево, переходим в начальное состояние
все повторяем сначала

Задача2: X div 2
-----------------
Идея: "Двигаться справа налево, заменять справа каждые две палочки на одну палочку до тех пор,
пока палочки не закончатся, если останется одна последняя палочка - стереть ее"

S1,0 -> S0,0,N;ЕСЛИ пустая клетка, остаться на месте, завершение работы
S1,1 -> S2,0,L;ИНАЧЕ первая палочка, стираем ее и проверим следующую клетку слева
S2,1 -> S3,1,L;ЕСЛИ вторая палочка, оставим ее и передвигаемся влево - продолжаем работу
S2,0 -> S0,0,N;ИНАЧЕ все палочки закончились, остаться на месте, завершение работы
S3,0 -> S0,0,N;Все палочки закончились, остаться на месте, завершение работы
S3,1 -> S4,0,L *;Опять палочка, стираем ее и проверим следующую клетку слева
S4,0 -> S0,0,N;Все палочки закончились, остаться на месте, завершение работы
S4,1 -> S5,0,L;Вторая палочка, стираем ее и проверяем есть ли еще палочки слева
S5,0 -> S6,0,R;ЕСЛИ Слева палочек больше нет, то двигаемся вправо чтобы прибавить к результату последнюю единицу
S6,0 -> S6,0,R; продолжаем двигаться вправо пока не встретим палочки - результат
S6,1 -> S7,1,L; встретили палочки - результат, вернемся на клетку влево
S7,0 -> S0,1,N; ставим палочку (прибавляем к результату последнюю единицу), остаться на месте, завершение работы
S5,1 -> S8,0,R;ИНАЧЕ Слева еще есть палочки, двигаемся вправо чтобы прибавить к результату единицу
S8,0 -> S8,0,R; продолжаем двигаться вправо пока не встретим палочки - результат
S8,1 -> S9,1,L; встретили палочки - результат, вернемся на клетку влево
S9,0 -> S10,1,L; ставим палочку (прибавляем к результату единицу) и двигаемся влево до оставшихся палочек
S10,0 -> S10,0,L; продолжаем двигаться влево пока не встретим оставшиеся палочки
S10,1 -> S3,1,N;Вернулись к оставшимся палочкам, продолжаем работу
продолжение работы со строчки, помеченной *

Список исочников в интернете

1. http://alnam.ru/book_laa.php?id=87

2. http://xn--80aawbkjgiswr.xn--1-btbl6aqcj8hc.xn--p1ai/articlef.php?ID=200600802

3. http://rpp.nashaucheba.ru/docs/index-47746.html

4. http://www.cyberforum.ru/automata-theory/thread523912.html

5. http://ru.wn.com/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0

Дата добавления: 2015-08-17