В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 46
Текст из файла (страница 46)
Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа их, пусты. Будем говорить, что непустое слово в в алфавите А'1(а» = = (ап ..., а„» воспринимается машиной в стандартном положении, еслй это слово записано в последовательных ячейках ленты, все другие ячейки пусты и машина обозревает крайнюю справа ячейку из тех, в которых записано слово в.
Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии а, (соответственно в состоянии остановки аь). Далее будем говорить, что слово ю перерабатывается машиной в слово о, если от слова ю, воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову о, воспринимаемому в положении остановки. Пусть на некотором множестве слов алфавита (а„..., а,» задана к-местная функция, значениями которой являются слова в том же алфавите. Предположим, что имеется машина Тьюринга с алфавитом А = (а, а„..., а„» (и > 1), которая любой набор из /с слов, входящий в область определения функции, записанный на ленту последовательно с промежутками в одну ячейку между словами, перерабатывает в слово, являющееся значением функции на этом наборе, а на любом наборе из к слов, не входящем в область определения функции, машина работает бесконечно.
Тогда про такую машину Тьюринга говорят, что она вычисляет данную функцию, а сама функция называется вычислимой по 2'ьюрингу или (короче) вычислимой. Применение машин Тьюринга к словам. Решить задачи 12.1— 12.11. 12.1. Имеется машина Тьюринга с внешним алфавитом А = = (а, 1», алфавитом внутренних состояний Д = (ды а,» и функциональной схемой (программой). В столбце дь ничего не написано, потому что а, — заключительное состояние машины„т.е.
такое состояние, оказавшись в котором машина останавливается. Функциональную схему или 222 программу кратко можно записать в виде последовательности из двух команд: ч!ао -+ д01, й1 -+ д~1П. Определите, в какое слово перерабатывает машина каждое из следующих слов, если она находится в начальном состоянии д, и обозревает указанную ячейку: а) 1а011ааа011 (обозревается ячейка 4, считая слева); б) 11аа111а01 (обозревается ячейка 2); в) 1а0аа111 (обозревается ячейка 3); г) 1111ц,11 (обозревается ячейка 4); д) 1!ар!111 (обозревается ячейка 3); е) 1111111 (обозревается ячейка 4); ж) 11111 (обозревается ячейка 5); з) 111...1 (к единиц, обозревается к-я ячейка). Изобразите схематически последовательность конфигураций, возникающих на ленте на каждом такте работы машины.
Р е ш е н и е. а) Изобразим схематически начальную конфигурацию (начальное положение машины): ! а 1 ! а а, 1 1 Схема означает, что машина находится в состоянии д, и обозревает ячейку, в которой записана буква 1, в соседней слева ячейке записана та же буква, а в соседней справа ячейке записана буква аа (т.е. согласно нашему соглашению ничего не записано) и т.д. Ничего не записано и во всех непоказанных ячейках ленты. На первом такте работы согласно команде д,! -+ д,1П машина остается в прежнем состоянии 1, в обозреваемую ячейку вписывает букву 1 (т.е.
фактически оставляет уже вписанную в эту ячейку букву 1 неизменной) и переходит к обозрению следующей правой ячейки (т.е. ячейки 5). Изобразим схематически положение, в котором оказалась машина: ! а 1 ! а а ! ! На втором такте работы согласно команде д,а0 -э д01 машина вписывает в обозреваемую ячейку 5 букву 1, продолжает обозревать туже ячейку и переходит в состояние 0„ т.е. останавливается. Создавшаяся конфигурация имеет вид: чо ! а ! ! ! а ! ! Таким образом, из данного начального положения слово 1ар11а0а,11 перерабатывается машиной в слово 1а0111аа11. 223 12.2. Дана машина Тьюринга с внешним алфавитом А = (ое, Ц, алфавитом внутренних состояний 0 = (дм дь дн 93 Д4 45 46 97) и со следующей функциональной схемой (программой): Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из начального стандартного положения: а) 11111; б) 111111; в) 1111; г) 1111111; д) 111; е) 1аю111аоаю1111; ж) 11аеао111111; з) 11ае111.
Р е ш е н и е. д) Выписываем последовательность конфигураций машины при переработке ею слова 111 из начального стандартного положения: 7) 8) 2) 9) 3) 10) 4) 5) 6) 12) Итак, слово 111 из начального стандартного положения перерабатывается машиной в слово 1. 12.3. Запишите программу (функциональную схему) машины Тьюринга из задачи 17.2: а) в виде последовательности команд; б) в виде сокращенной таблицы; в) в виде сокращенной последовательности команд. Р е ш е н и е. б) Сокращение достигается за счет следующих соглашений: если состояние машины после выполнения команды не меняется, то мы его второй раз не пишем в команде„аналогично, если команда вписывает в ячейку ту же самую букву, что и была записана там, то эту букву второй раз в команде не пишем.
224 Сокращенная таблица, представляющая собой программу машины из предыдущей задачи, имеет тогда следующий вид: 12.4. Машина Тьюринга задается следующей функциональной схемой: Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из начального стандартного состояния. После этого постарайтесь усмотреть общую закономерность в работе машины: а) 111ю111; б) 1111*11; в) 111ю1; г) 1ю11; д) 11*111; е) 11111ю; ж) *1111. Р е ш е н и е. г) Запишем последовательность конфигураций: 1*1д~1 =' 1юдз1юзо =' 1дз*1аю =' дз1*1аю =' дзао1*1ао ~ 1дз1*1аю ~ 11дзю1ао =' 11юдз1ао ~ 11ю1дзао 11юд11ао ~ 11дз*аоао =' ~ 1дз1«аоао =' дзН .аоао => дзао11юаоао =' 1дз11юаоаа ~ 11дз1*ааззо ~ =' 111дз*юзоао =' 111юдзаоюзо ~ 111й*аоззо =' 111до«огзоао.
Проделайте самостоятельно преобразования остальных слов. Мы видим, что каждое из них перерабатывается в слово, состоящее из такого количества единиц, записанных подряд, сколько их было в исходном слове записано вместе по обе стороны от разделительной звездочки. Таким образом, машина фактически осуществляет сложение единиц. Каков же алгоритм этого сложения? Машина стирает первую единицу, обозреваемую в начальном положении д„и ее головка движется по ленте влево до первой пустой ячейки, в которую машина помещает единицу. (Машина как бы берет самую правую единицу и переносит ее в левый конец слова.) В нашем случае имеем 1ю1д,1 ~ 11юд,а„т.е. за один этот цика машина вернулась в свое исходное положение, но для другого начального слова: 11ю1. Затем машина проделывает второй цикл: берет крайнюю правую единицу, относит ее на левый край и возвращается в исходное положение 111д,*, при котором теперь в обозреваемой ячейке содержится не 1, аю. Машина стирает ее и останавливается.
8 игоанн 225 Нетрудно подсчитать количество шагов (тактов), которое проделывает машина при решении задачи по данному алгоритму. Если слева от звездочки записано и единиц, а справа — и, то на каждый цикл машина затрачивает 2(т+ и+ 1) тактов. Чтобы перенести п единиц, нужно проделать и циклов и, значит, совершить 2л(т+ л+ 1) тактов работы. В связи с этим возникает проблема разработки более быстрого алгоритма, решающего ту же задачу сложения единиц, разделенных звездочкой на ленте машины Тьюринга.
Такой алгоритм мог бы дейсз вовать, например, следующим образом. Начав из стандартного начального положения, сразу же стереть единицу и двинуться влево. Дойдя до звездочки, заменить ее на единицу. Все. Если же в начальном стандартном положении обозревается звездочка, то просто стереть ее и остановиться. Проверьте, что этот алгоритм для слов указанного вида реализует машина Тьюринга со следующей программой: д~ — ~ дза0Л, др -+ 40аа, др1 -+ д,1Л, дз~ -+ да1. Количество тактов здесь для выполнения сложения фактически равно числу п единиц в правом слагаемом.
Придумайте свой алгоритм, решающий эту задачу (см. задачу 12.34, а). 12.5. Машина Тьюринга определяется следующей функциональной схемой: Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из стандартного начального состояния: а) 111*11; б) 11е11; в) 1111*1; г) 11111~111; д) 11111*1111. Постарайтесь выявить общую закономерность в работе машины.
Р е ш е н и е. Выписав последовательности конфигураций, получаемых при переработке машиной слов а), б), в), мы придем соответственно к следующим результатам: 1, а,, 111. Создается впечатление, что программа осуществляет вычитание числа и единиц, стоящих правее звездочки, из числа т единиц, стоящих левее звездочки, когда е > и. При этом алгоритм работает следующим образом. Машина стирает первую (самую правую) единицу, обозреваемую в начальном состоянии дь и ее головка движется по ленте влево, достигает звездочки, переходит через нее и упирается в первую единицу.
Стирает ее и возвращается к правому концу слова, на котором стирает следующую крайнюю единицу и 22б снова движется влево, до ближайшей единицы левее звездочки, стирает ее, и т.д. Идея данного алгоритма хороша, но она не реализуется в полном объеме рассматриваемой машиной Тьюринга. В самом деле, посмотрим, как перерабатывается данной машиной слово г) (некоторые очевидные шаги пропущены): 11111«11Ч!1 11111*14721110 11111Ч2»11120 11114731'"11120 =' 1111аоЧ4«11ао ~ 1111ао»47411ао ~ 1111ао«116400 ~ 1111ао»1%1ао ~ ~ 1111ао«д21аоао ~ 1111а0472«1аоао ~ 1111471ао«1аоао => 111412141о«1аоао ~ 1 1 1аоч4ао«1120120 1 421ао 0«1410120 1 1 1аоаоч1«1 0120 ~ 111 аоао47оао1аоао.
Машина остановилась, но на ленте осталась «недосчитанной» разность 3 — 1. Если применить данную машину к слову д) 11111»1111, то получим в итоге слово 111аоаоао11аоао, т.е. «недосчитанной» остается разность 3 — 2. Анализируя работу данной программы, приходим к выводу. Если т > л > 3, то программа будет стирать по 2 единицы справа из каждого массива единиц, разделенных звездочкой; будет стерта и сама звездочка. Таким образом, на ленте останется записано слева т — 2 единицы, справа и — 2 единицы, разделенных тремя пустыми ячейками.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
