Опишите машину Тьюринга, проверяющую, что x есть начало последовательности 0110111001011101111000...(все числа записаны подряд по возрастанию в двоичной записи). Поясните, почему эта программа работает правильно. (При написании программы можно предполагать, что машина имеет 2 завершающих состояния: принимающее q<sub>a</sub> и отвергающее q<sub>r</sub>. Если машина приходит в одно из этих состояний, то вычисление останавливается, а ответ считается данным не зависимо от состояния ленты. Таким образом, нет необходимости "удалять мусор").

задан 3 Май 20:24

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

Здесь общая схема понятна, хотя реализация в виде программы требует времени и труда :)

В процессе работы машина должна слева от основной записи иметь "шпаргалку" в виде "текущего" двоичного числа, совпадение с которым соответствующего фрагмента основной записи она проверяет. Если где-то произойдёт несовпадение, то машина останавливается. Поэтому будем нацелены на тот случай, когда требуемые совпадения всё время происходят.

В начале пишем 0 перед числом x через пустой символ. В процессе работы машина делает "сверку", и время от времени от записи числа слева переходит к следующему в двоичной записи. Такой переход легко осуществляется с помощью подпрограммы. Понятно, как она устроена. Например, у нас было написано 10111. Машина справа налево от конца записи заменяет все 1 на 0, пока не дойдёт до 0 или пустого символа, меняя его на 1.

В том месте, где машина находится в пределах записи x, она должна запомнить место. Это делается заменой символа на пустой, с переходом в одно из состояний, которое "помнит", что машина стёрла. От этого места головка идёт влево к "шпаргалке". На первом шаге нового цикла (считаем, что у нас только что появилось число 11000 в "шпаргалке"), машина стёрла 1 в записи x, запомнила это, и идёт к крайнему слева символу "шпаргалки", который она легко находит (по принципу, что левее него пустой символ). Находя, она его сверяет, и затем стирает, чтобы запомнить место. Какой это был символ, она помнит по состоянию. В случае успеха, она идёт вправо и находит место стёртой единицы. По состоянию она помнит, что было стёрто, восстанавливает его, и стирает следующий символ. Заметим, что по состоянию она теперь должна запомнить две вещи -- что было стёрто там и там.

После этого машина повторяет действие в цикле: идёт к "шпаргалке", находит пустой символ, который был стёрт, восстанавливает его, и сверяется с очередным, после чего его стирает. Так происходит движение по "шпаргалке", и в какой-то момент мы достигнем её конца, что распознаётся. Тогда надо включить подпрограмму перехода к двоичной записи числа, на единицу большего данного, что уже было описано. Далее снова вправо, находя стёртый символ в записи x, восстанавливая его, и переходя к следующему справа, входя в очередной цикл. Если справа ничего нет, то запись x вся просмотрена, и надо остановиться в состоянии принятия (это касается и всех промежуточных шагов тоже).

ссылка

отвечен 4 Май 2:19

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

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

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

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

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

отмечен:

×883
×52

задан
3 Май 20:24

показан
63 раза

обновлен
4 Май 2:19

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

по почте:

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

по RSS:

Ответы

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

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