Применение машин тьюринга к словам
КОНСТРУИРОВАНИЕ МАШИН ТЬЮРИНГА
жүктеу/скачать 344.5 Kb.
|
КОНСТРУИРОВАНИЕ МАШИН ТЬЮРИНГА5.13. Известно, что на ленте записано слово  ; n 1. Постройте машину Тьюринга с внешним алфавитом А = {а0, 1}, которая отыскивала бы левую единицу этого слова (т. е. приходила бы в состояние, при котором обозревалась бы ячейка с самой левой единицей данного слова, и в этом положении останавливалась), если в начальный момент головка машины обозревает одну из ячеек с буквой данного слова.
5.14. Сконструируйте машину Тьюринга с внешним алфавитом А = {а0, 1}, которая каждое слово в алфавите А1 = {1} перерабатывает в пустое слово, исходя из стандартного начального положения. Указание. В алфавит внутренних состояний включите четыре буквы Q= {q0, q1, q2, q3}. 5.15. Сконструируйте машину Тьюринга с внешним алфавитом А = {а0, 1}, которая каждое слово длиной п в алфавите A1 = {1} перерабатывает в слово длиной п + 1 в том же алфавите А1. Указание. Используйте алфавит внутренних состояний из двух букв. См. задачу 5.1. 5.16. На ленте машины Тьюринга записаны два набора единиц 1. Они разделены звездочкой *. Составьте функциональную схему машины так, чтобы она выбрала больший из этих наборов, а меньший стерла, исходя из стандартного начального положения (см. задачу 5.2). Звездочка должна быть сохранена, чтобы было видно, какой из массивов выбран. Указание. Машина может работать, например, следующим образом. Заменить крайнюю правую единицу на и из состояния q1 перейти в состояние q2, в котором она должна, ничего не меняя, прошагать к крайней левой единице. Здесь, перейдя в состояние q3, заменить крайнюю левую единицу на букву . Далее, перейдя в состояние q4, прошагать к крайней правой единице, ничего не меняя. Здесь снова заменить единицу на букву и вернуться к крайней левой единице и т. д. Дальше программа имеет разветвление. Если, начиная двигаться с правого конца, машина в состоянии q1, сделав шаг влево, обозревает ячейку с буквой *, то это означает, что единицы правого массива иссякли. Следовательно, левый массив больше. Тогда машина, перейдя в состояние q5. проходит ячейку с буквой * и во всех последующих ячейках слева проставляет единицы. Затем в состоянии q6 она возвращается к ячейке со *, минует ее и следует дальше вправо, стирая содержимое ячеек (там записаны буквы ). Дойдя до первой пустой ячейки, машина останавливается. Если же, начиная двигаться с левого конца, машина в состоящий q3 сделав шаг вправо, обозревает ячейку с буквой *, то это означает, что иссякли ед 5.17. Постройте машину Тьюринга, которая бы к натуральному числу в десятичной системе счисления прибавляла единицу. Р е ш е н и е. В качестве внешнего алфавита естественно выбрать алфавит, содержащий наименования всех цифр десятичной системы счисления. Конечно же, необходим и пустой символ а0. Итак, А ={ а0, 1 2, 3, 4, 5, 6, 7, 8, 9, 0}. Состояний у машины будет два: q0 (это, как обычно, остановка) и q1 (рабочее состояние). Итак, Q = {q0, q1}. Функциональная схема {программа) машины:
Начальное положение машины стандартное. Читателю предлагается проанализировать работу машины. 5.18. По аналогии с предыдущей задачей составьте функциональную схему машины Тьюринга, которая бы от натурального числа в десятичной системе счисления отнимала единицу. 5.19. Дана конечная совокупность единиц, вписанных в ячейки, взятые подряд без пропусков. Постройте функциональную схему такой машины Тьюринга, которая записывала бы в десятичной системе число этих единиц, т. е. пересчитывала бы набор единиц. 5.20. На ленте записаны два числа в двоичной системе счисления, разделенные звездочкой:
Определите, какую операцию проделает с ними машина Тьюринга, начиная из стандартного положения (крайняя правая ячейка, состояние q1), если программа машины задается таблицей:
5.21. Вопрос, аналогичный вопросу из предыдущей задачи, для ленты
и для машины Тьюринга с программой:
5.22. На ленту подряд вписаны два конечных набора единиц, разделенные звездочкой. Составьте программу машины Тьюринга, которая выписывала бы подряд, без разделения звездочкой, столько единиц, сколько их в обоих наборах (сложение единиц). Указание. См. задачу 5.3. 5.23. На ленту подряд вписаны два конечных набора единиц, разделенные звездочкой. Причем в левом наборе единиц больше, чем в правом. Составьте программу машины Тьюринга, которая в левом наборе оставляла бы ровно столько единиц, на сколько единиц в левом наборе больше, чем в правом, а все остальные единицы стирала бы (вычитание единиц). Указание. См. задачу 5.4. 5.24. Два конечных набор а. из т и n единиц записаны на ленту подряд. Машина в: начальном положении обозревает крайнюю правую единицу левого набора. Постройте программу машины Тьюринга, которая выдавала бы набор единиц из НОД (m, п) штук, а остальные единицы, стирала бы. Указание. Используйте алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел и запрограммируйте его для машины Тьюринга. См. задачу 5.5. 5.25. Постройте машину Тьюринга, осуществляющую перевод слова  в слово  . Причем в начальном положении машина должна находиться в состоянии q1 и обозревать первую ячейку, эту же ячейку она должна обозревать и в момент остановки. (Эта машина называется «перенос нуля» и обозначается А.)
Решение. Приводим программу машины. Рядом с командами изображаем конфигурации, получающиеся в результате выполнения соответствующих команд:
Проанализируйте работу машины. 5.26. Постройте машину Тьюринга, перерабатывающую слово  в это же слово из стандартного начального положения, причем в момент остановки должна обозреваться крайняя левая ячейка. (Эта машина называется «левый сдвиг» и обозначается Б.)
5.27. Условие аналогично условию предыдущей задачи, но в начальном положении должна обозреваться крайняя левая ячейка, а конечное положение стандартно. Эта машина называется «правый сдвиг» и обозначается Б+.) Указание. Программа этой машины получается из программы Б заменой символа Л символом П. 5.28. Постройте машину Тьюринга (называемую «транспозиция» и обозначаемую В), которая перерабатывает слово  в слово  , причем в начальном и конечном положении обозревается ячейка, содержащая 0, между двумя наборами единиц.
5.29. Постройте машину Тьюринга (называемую «удвоение» и обозначаемую Г), которая перерабатывает слово в слово  , причем в начальном и конечном положении обозревается крайняя левая ячейка.
5.30. Постройте машину Тьюринга, переводящую слово  в слово  , причем в начальном положении обозревается ячейка с 0 между наборами из у и z единиц, а в конечном положении обозревается ячейка с 0 между наборами из г и х единиц. (Эта машина называется «циклический сдвиг» и обозначается Ц3.)
Указание. Проверьте, что такой перевод произойдет в результате последовательного применения (композиции) ранее построенных машин В, Б и В, т. е. Ц3 = ВБВ. Решение. В самом деле, введем обозначение ВБВ(01x01y01z0) = ВБ (В (01x01y01z0)) = ВБ (01x01z01y0) = В(Б (01x01z01y0)) = = В(01x01z01y0)) = ) = 01z01x01y0.
Указание. Проверьте, что эта машина представляет собой следующую композицию построенных выше машин: жүктеу/скачать 344.5 Kb. Достарыңызбен бөлісу:
|
и вычислим: