Другие языки программирования и технологии

Алгоритм на машине Тьюринга

Есть задание: скопировать два числа, записанных в двоичной форме, но так, чтобы они поменялись местами.
Например, 110 101 -> 101 110.
Пожалуйста, объясните, как составить такой алгоритм. 3 дня пытаюсь разобраться с машиной Тьюринга, но вообще не могу понять, как сделать, чтобы алгоритм работал для любых двоичных чисел, любой длины. Не понимаю, как объяснить машину 0 или 1 ей переносить и куда именно.
Amil Rzayev
Amil Rzayev
950
Надо перенести первое число вправо от второго. А "объяснить" - это использовать разные состояния. У тебя будет два почти идентичных набора состояний, отличающихся только тем, какое число ставим последним действием. Примерно так:

Q1, 0 -> Q2, пусто, вправо
Q1, 1 -> Q5, пусто, вправо
Q1, пусто -> стоп
Q2, 0 -> вправо
Q2, 1 -> вправо
Q2, пусто -> Q3, вправо
Q3, 0 -> вправо
Q3, 1 -> вправо
Q3, пусто -> Q4, вправо
Q4, 0 -> вправо
Q4, 1 -> вправо
Q4, пусто -> Q8, 0, влево
Q5, 0 -> вправо
Q5, 1 -> вправо
Q5, пусто -> Q6, вправо
Q6, 0 -> вправо
Q6, 1 -> вправо
Q6, пусто -> Q7, вправо
Q7, 0 -> вправо
Q7, 1 -> вправо
Q7, пусто -> Q8, 1, влево
Q8, 0 -> влево
Q8, 1 -> влево
Q8, пусто -> Q9, влево
Q9, 0 -> влево
Q9, 1 -> влево
Q9, пусто -> Q10, влево
Q10, 0 -> влево
Q10, 1 -> влево
Q10, пусто -> Q1, вправо

Q1 - анализ первой цифры левого числа, стирание этой цифры и переход к нужной ветке, Q2-Q4 - перенос нуля, Q5-Q8 - перенос единицы, Q9-Q11 - сдвиг влево к первой цифре первого числа.
D\
Dead \m/
86 145
Лучший ответ
Amil Rzayev Спасибо!
Машина Тьюринга это алгоритмическая абстракция. Какой от неё практический толк?
Александр Л
Александр Л
37 945
Dead \m/ Это теория, которая лежит в основе всех алгоритмов. И которая очень хорошо развивает нужное программисту мышление.

Похожие вопросы