Последовательность неотрицательных целых чисел (x1,x2,…, xn) задается на ленте машины Тьюринга как слово 01x101x2…01xn, где 1x обозначает слово 11…1, состоящее из x единиц (остальные клетки ленты заполнены «мусором», то есть заранее неизвестными символами алфавита).
Требуется построить машину Тьюринга, осуществляющую заданные ниже преобразования.
Предполагается, что в начале работы машина, находится в стандартном состоянии, то есть, головка показывает на 0 перед крайней левой единицей исходных данных и машина находится в состоянии q1.
По окончании работы алгоритма также предусмотреть стандартное состояние машины, то есть, головка показывает на 0 перед крайней левой единицей результата и машина находится в состоянии q0
4. а) (x1,x2)→(x1,x2, x2,x1)
б)(x1,x2)→x2-x1 при x1<x20 в других случаях
Решение
А) x1,x2→x1,x2, x2,x1
Таким образом, машина должна скопировать зеркально скопировать первый и второй массивы единиц в правую часть ленты после второго массива единиц.
Опишем кратко алгоритм: ставим перед начальным положением головки 0, тем самым обозначая начало массивов двумя 0, затем находим окончание второго массива – 0, заменяем 0 на 1, следующий символ приравниваем 0, и начинаем переносить последовательно символы сначала со второго массива (заменяя единицы нулями), а потом и первого массива. После ввода последнего символа, возвращаемся к концу второго массива и меняем числа на противоположные, до тех пор пока не дойдем до двух нулей – окончание работы.
Таблица состояний:
0 1
q1 0 q2 L
q2 0 q3 R 0 q3 R
q3 0 q3 R 1 q4 R
q4 0 q5 R 1 q4 R
q5 0 q6 R 1 q5 R
q6 0 q7 L 0 q7 L
q7 1 q8 L
q8 0 q8 L 0 q9 L
q9 1 q14 R 1 q10 R
q10 0 q10 R 1 q11 R
q11 1 q12 R 1 q11 R
q12 0 q13 L 0 q13 L
q13 0 q8 L 1 q13 L
q14 0 q14 R 1 q15 R
q15 1 q16 R 1 q15 R
q16 0 q17 R 0 q17 R
q17 0 q18 L 0 q18 L
q18 0 q19 L 1 q18 L
q19 0 q20 L 1 q19 L
q20 0 q20 L 1 q21 L
q21 0 q21 L 0 q22 L
q22 0 q28 R 1 q23 R
q23 0 q23 R 1 q24 R
q24 0 q24 R 1 q25 R
q25 0 q26 R 1 q25 R
q26 1 q27 R 1 q26 R
q27 0 q18 L 0 q18 L
q28 1 q28 R 0 q29 R
q29 1 q29 R 0 q30 R
q30 0 q31 R 1 q30 R
q31 1 q32 R 1 q31 R
q32 0 q33 L 0 q33 L
q33 0 q34 L 1 q33 L
q34 0 q0 R 1 q33 L
Теперь запишем последовательность команд машины Тьюринга.
0 q1→0 q2 L сдвигаем на 1 символ влево
0 q2→0 q3 R ставим 0 и сдвигаемся в начальное положение
1 q2→0 q3 R
0 q3→0 q3 R проходим 0 перед первым массивом
1 q3→1 q4 R сдвигаемся на первую единицу первого массива
1 q4→1 q4 R сдвигаемся по всем единицам первого массива
0 q4→0 q5 R проходим первый ноль-разделитель, теперь головка показывает на первую единицу второго массива
1 q5→1 q5 R сдвигаемся по всем единицам второго массива
0 q5→0 q6 R проходим второй ноль-разделитель
0 q6→0 q7 L ставим 0 и сдвигаемся влево на второй ноль- разделитель
1 q6→0 q7 L
0 q7→1 q8 L заменяем ноль- разделитель на 1, сдвигаемся влево
Первый цикл
0 q8→0 q8 L сдвигаемся по всем 0 влево
1 q8→0 q9 L доходим до 1, заменяем ее на 0, сдвигаемся влево
1 q9→1 q10 R если слева 1, продолжаем цикл, сдвигаясь вправо
0 q10→0 q10 R сдвигаемся по всем нулям до первой единицы – второй разделитель
1 q10→1 q11 R проходим единицу-разделитель
1 q11→1 q11 R проходим по всем единицам вправо
0 q11→1 q12 R заменяем 0 на 1, сдвигаемся вправо
0 q12→0 q13 L ставим 0 и сдвигаемся влево
1 q12→0 q13 L
1 q13→1 q13 L сдвигаемся по всем единицам влево
0 q13→0 q8 L переходим через единицу-разделитель
Повторяем первый цикл
0 q9→1 q14 R если слева 0, мы дошли до начала второго массива, встретив 0-разделитель, первый цикл завершен, заменяем 0 на 1 и сдвигаемся вправо
0 q14→0 q14 R проходим по всем 0 вправо
1 q14→1 q15 R проходим первую единицу-разделитель
1 q15→1 q15 R сдвигаемся по всем единицам вправо
0 q15→1 q16 R доходим до нуля, заменяем его последней единицей второго скопированного массива и сдвигаемся вправо
0 q16→0 q17 R ставим 0, который будет разделителем между вторым и первым скопированным массивом, сдвигаемся вправо
1 q16→0 q17 R
0 q17→0 q18 L ставим 0, сдвигаемся влево
1 q17→0 q18 L
Второй цикл
1 q18→1 q18 L проходим по всем единицам влево
0 q18→0 q19 L проходим новый ноль-разделитель, сдвигаемся влево
1 q19→1 q19 L проходим по всем единицам влево
0 q19→0 q20 L
0 q20→0 q20 L проходим по всем нулям второго массива до единицы - разделителя
1 q20→1 q21 L проходим единицу – разделитель, сдвигаемся влево
0 q21→0 q21 L проходим по всем 0 первого массива влево
1 q21→0 q22 L доходим до единицы, заменяем ее на 0, сдвигаемся влево
1 q22→1 q23 R если слева 1, продолжаем цикл, сдвигаясь вправо
0 q23→0 q23 R сдвигаемся по всем нулям до первой единицы – первый разделитель
1 q23→1 q24 R проходим первую единицу-разделитель
0 q24→0 q24 R сдвигаемся по всем нулям до единицы – второй разделитель
1 q24→1 q25 R проходим единицу-разделитель
1 q25→1 q25 R с
0 q25→0 q26 R проходим ноль-разделитель между новыми массивами
1 q26→1 q26 R проходим по всем единицам вправо
0 q26→1 q27 R заменяем 0 на 1, сдвигаемся вправо
0 q27→0 q18 L ставим 0, сдвигаемся влево
1 q27→0 q18 L
Повторяем второй цикл
0 q22→0 q28 R если слева 0, мы дошли до начала первого массива, встретив 0-разделитель, второй цикл завершен, сдвигаемся вправо
0 q28→1 q28 R заменяем нули первого массива на 1, а единицы- разделители на 0
1 q28→0 q29 R
0 q29→1 q29 R
1 q29→0 q30 R
1 q30→1 q30 R проходим по всем единицам вправо
0 q30→0 q31 R проходим ноль-разделитель между новыми массивами
1 q31→1 q31 R проходим по всем единицам вправо
0 q31→1 q32 R заменяем 0 на 1, сдвигаемся вправо
0 q32→0 q33 L заменяем 0 на 1, сдвигаемся влево
1 q32→0 q33 L
0 q33→0 q34 L двигаемся влево, пока не встретим два подряд идущих нуля, вернемся на шаг вправо – мы достигли состояния q0
1 q33→1 q33 L
1 q34→1 q33 L
0 q34→0 q0 R
Алгоритм завершен.
б) (x1,x2)→x2-x1 при x1<x20 в других случаях
От второго массива последовательно с конца отнимаем единицы первого массива, затем переносим оставшиеся единицы второго массива начальную позицию (слева от первого 0)
Задать вопрос
на новый заказ в Автор24.
