задан 19 Июн '14 19:52

изменен 19 Июн '14 22:36

Deleted's gravatar image


126

10|600 символов нужно символов осталось
2

Поскольку определение машины Тьюринга и правила её работы могут несколько варьироваться, я ограничусь описанием процесса. Всё сводится к такой задаче: имеется строка из $%n$% единиц, нужно переработать её в строку из $%3n$% единиц. Например, 11 должно быть превращено в 111111, и так далее.

Процесс выглядит так: стираем по одной единице с левого края, пока они есть, и потом вместо неё дописываем в конец строки 3 единицы. Две образующиеся при этом группы единиц разделяются нулём. Так, если сначала было 1111, то после одного прохождения цикла должно стать 1110111, после следующего -- 110111111, далее 10111111111, и так далее.

Реализуется это несложно: в состоянии $%q_0$% видим 1, переходим в $%q_1$%, пишем 0 вместо 1, сдвигаемся вправо. Это действие может быть записано в виде команды $%q_01q_10R$%. Далее пропускаем все единицы, оставаясь в том же состоянии, двигаясь вправо. Это команда $%q_11q_11R$%, она выполняется несколько раз.

После прохождения единиц мы встречаем 0, переходя в состояние $%q_2$% и перемещаясь вправо. Команда имеет вид $%q_10q_20R$%. Теперь надо пройти сквозь все написанные справа единицы. На самом первом шаге их не будет, но команда всё равно нужна (просто на самом первом шаге она не будет применена). Это $%q_21q_21R$%. В итоге мы дойдём до нуля, и надо приписать три единицы. Это команды $%q_20q_31R$%, $%q_30q_41R$%, $%q_40q_51L$%. Теперь мы в состоянии $%q_5$% продвигаемся влево, пропуская все единицы: $%q_51q_51L$%. Доходим до нуля, который разделяет две группы единиц, и переходим в новое состояние: $%q_50q_60L$%.

Теперь всё зависит от того, какой символ мы видим. Если это 0, то мы всю работу выполнили, и надо перейти в состояние, ведущее к остановке (выполнив при этом, возможно, несколько финальных действий типа установления головки в нужную позицию). Для этой цели в программе будет команда $%q_60q_70R$%. Если же мы видим 1, то переходим в другое состояние, двигаясь влево, а затем пропуская все единицы. Получится $%q_61q_81L$% и $%q_81q_81L$%. Рано или поздно доходим до нуля, и тогда надо сдвинуться вправо, переходя в начальное состояние $%q_0$% и "зацикливая" тем самым машину: $%q_80q_00R$%. После этого она начнёт повторять то, что делала в начале, стирая слева одну единицу и вместо неё дописывая три единицы справа, и так далее.

ссылка

отвечен 19 Июн '14 20:45

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,926

задан
19 Июн '14 19:52

показан
1649 раз

обновлен
19 Июн '14 20:45

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru