Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 36
Текст из файла (страница 36)
а (т раз) и [а]ы будем писать аы. Через И' будем обозначать произвольное конечное слово во внешнем алфавите машины Тьюринга (в частности, пустое, т. е, состоящее из пустых символов внешнего алфавита). При описании работы машины Тьюринга «на языке конфигураций» будут использоваться выражения, аналогичные такому: уз1а01 "ОИ' [-. 1 "ОдвИг, и > 1 и у > 1. Приведенное выражение надо понимать так: машина «стирает» слово 1' и останавливается на первой букве слова И', если же И' — пустое слово, то «останов» происходит на втором 0 (нуле) после слова 1". Машины Тьюринга Т, и Тз называются эквивалентными (в алфавите А), если для всякого входного слова Р (в алфавите А) выполняется соотношение Тг(Р) = Тз(Р), означающее следующее: результаты Тз(Р) и Тз(Р) определены или не определены одновременно (т.е.
машины Тз и Тз либо обе применимы, либо обе не применимы к слову Р) и, если зти результаты определены, Т,(Р) = Тз(Р). Символ = называется знаком условного равентпви Пример 1. Выяснить., применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то выписать результат применения машины Т к слову Р (считается, что дз начальное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте): 182 Гл. К Эаемен~пм теории аиеоритмое Решение.
а) Исходя из конфигурации ц110з1 получаем последовательно такие конфигурации: цгО 1, 1цяО 1, 1~цзОз1, 1зОц10 1, 1Я01цз01, 1Я01зцз1. Так как команды вида цз1ейа11 в программе П нет, то последняя конфигурация (т. е, 1з01зцз1) заключительная. Следовательно, машина Т к слову Р = 10з1 применима, и Т(Р) = 1з01 . б) Выписывая конфигурации, имеем цг[10)Я1, цзОз101, 1цзОз101, 1~цз[ОЦ~, 1 Оцг101, 1 ц1 0~1, 1зцзО 1, 1~цз01, 1 Оц11, 1 а10, 1зцзО, 1ецзО, 1еОцзО, 1е01цзО, 1е01зцзО, 1е01зОцзО, 1е01з01цзО, 1е01з01зцзО и т.д, Ясно, что этот процесс продолжается неограниченно.
Значит, машина Т к слову Р = [10)з1 не применима. Пример 2. Построить в алфавите ~0, 1) машину Тьюринга, которая применима к словам вида 1зти 01~о+~ (т > 0 и и > 0) и 1з 01зи (п~ > 1 и ц > 1) но не применима к словам вида 1з 01з" и 1зи "01зи' (т > 1 и и > 1). (К словам иного вида мап|ина может быть как применима, так и не применима.) Решение.
Предполагаем, что цг --- начальное состояние, цо —. заключительное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте. Попытаемся реализовать в «конструируемой» машине следующую идею: машина «запоминает», четным или нечетным является число единиц в первом единичном массиве слова,и затем «сравнивает» эту характеристику с такой же характеристикой второго единичного массива. Пара команд цз1цз1Л и цз1ц11Л позволяет «выяснить» четностьнечетность числа единиц в первом единичном массиве: если на «промежуточном» нуле головка оказывается в состоянии цы то число единиц в первом единичном массиве четное, а если она оказывается в состоянии цз, то число единиц в этом массиве нечетное.
Проходя промежуточный нуль, нужно «запомнить», четное или нечетное число единиц было в первом массиве, чтобы после прохождения второго единичного массива в случае совпадения «четностей» числа единиц в двух массивах машина остановилась, а в ином случае не остановилась. Поэтому оба состояния цз и цз «сменим»: рассмотрим команды ц10цзОЛ и цзОц40Л. Второй единичный массив будем «просматривать» с помощью состояний цз и це: цз1ц41Л, це1цз1Л. Если первый единичный массив «четный», то просмотр второго единичного массива будет начат в состоянии цз. В случае, когда второй массив тоже четный, на первый нуль за этим массивом головка «выйдет» в состоянии цз, и машина должна остановиться.
Значит, можно взять команду вида цзОцоиР (м 6 (О, Ц и Р е Е (Я, Ь, Л)) либо не включать в программу ни одной команды, начинающейся с символов цз и О. Если же первый единичный массив четный,. а второй нечетный, то на первый нуль после второго массива головка выйдет в состоянии це, и машина не должна остановиться.
Поэтому берем команду цеОц405. Аналогично рассматривается случай с нечетным первым единичным массивом. 183 1 д Машины Тьюринга и операции над ниии Подходящая машина задается программой Чг1Чг1Л Чз1Ч41Л Чг1Ч41Л Ч41Чз1Л ч,оч,ол ч,оч,ол ЧгОЧ40Л 1.1. Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то выписать результат применения машины Т к слову Р.
Предполагается, что Чг начальное состоЯние, Че заключительное состоЯние и в начальный момент головка машины обозревает самую левую единицу на ленте: ч,оч,ол 1) П: Ч,1Ч,ОЛ а) Р = 1з01; б) Р = 1гог1. в) Р = 1е: Ч,1Ч,ОЛ Чг ОЧе1о ЧгОЧг1Ь 2) П. Ч41Чг1Л а) Р = 1'Ог1; Чг1Ч11Л б) Р = 14; в) Р = 1г01з; Ч10Чг1Л ЧгОЧЗ 1 Л Чг1ЧЗОЛ Чз1Ч41Л Ч,ОЧ,1Л Ч,1Ч,ОЛ Ч,ОЧ, 1Л Чг1Ч31-о ЧзОЧ, 1.~, а) Р = 1зЩг. б) Р = 14. в) Р 1г[01)г. 3) П: а) Р = [10)г1;. б) Р 10г1г. ) Р 10з1. 4) П: Ч10Чг1Л Ч41Чг1Л а) Р =1' б) Р = 1'0'1 в) Р =10'1. Чг1Ч401, ЧзОЧг1Л Чз1ЧоОА 5) П: 1.2. Построить в алфавите 10, 1) машину Тьюринга, обладающую следующими свойствами [предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустого символа берется 0): 1) машина имеет одно состояние, одну команду и применима к любому слову в алфавите 10, 1); 184 Гл.
1е. Элементы теорем алгоритмов 2) машина имеет две команды, не применима ни к какому слову в алфавите (О, 1) и зона работы на каждом слове бесконечная; 3) машина имеет две команды, не применима ни к какому слову в алфавите (О, 1) и зона работы на любом слове ограничена одним и тем же числом ячеек, нс зависящим от выбранного слова; 4) машина имеет три команды, применима к словам 102м1 (и ) 1) и не применима к словам 102в+ 1 (и > 0); 5) машина имеет пять команд, применима к словам 12" (и ) 1) и не применима к словам 12"+е (о = 1, 2 и и ) 0); 6) машина применима к словам 1м01", где и > 1, и не применима к словам 1"'01", где ие ~ и, т ) 1 и и > 1. 1.3.
По заданной машине Тьюринга Т и начальной конфигурации К1 найти заключительную конфигурацию (Чо -- заключительное состояние); Ч,ОЧ,1Л 1) Т. 0 1о а) К1 = 1201Ч11г. б) К1 101Ч1012 Ч2 Чо Ч2 1Ч1 11' Ч,ОЧ,Ы Ч11Ч21К а) К1 = 1Ч101; б) К1 = 1Ч11; з. л. Чг 1Ч1 ОЛ Ч,ОЧ.ОТ, 2) Т: Ч,ОЧ,ОТ, Ч, 1Ч,ОЛ Ч20Ч21А Ч21ЧоОК а) К1 10зЧ101. б) К1 1гЧ11з01 Ч1 ОЧо1~ Ч1 Чг ) К 12 1201. б) К 1 14. Ч,ОЧ,ОЛ Ч2 1Ч2 1е 4) Т: Ч,ОЧ,ОЯ Ч1 1 Чг 1 -' е Ч20Чо11 в. 3 4 Ч21Ч,ОЛ а) К1 = 1Ч11': б) К1 = Ч11 01; в) К1 = 10Ч11 . Ч,ОЧ,11, Ч,1Ч,ОК 5) Т: 1.4. Построить в алфавите (О, 1) машину Тьюринга, переводящую конфигурации К1 в конфигурации Ко1.
1) К1 = Ч11 Ко = Чо1 01 (и ) 1)' 2) К1 = Ч10" 1", Ко = Чо[01)м (и, > Ц; 1 5 Машины Тошринеа и операции над ниии 185 3) Кз = 1"410, Ко = цо1'" ?и > 1); 4) К1 =1"4101п', Ко = 1 до01" (гп > 1, п > 1). 1.5. 1) Показать, что для всякой машины Тьюринга существует эквивалентная ей машина, в программе которой отсутствует символ Я.
2) Показать, что по всякой машине Тьюринга можно построить эквивалентную ей машину, в программе которой не содержится заключительных состояний. 1.6. Показать, что для всякой машины Тьюринга Т в алфавите А существует счетно-бесконочное множество эквивалентных ей машин Т„рз, ..., Т„„... в том же алфавите А, отличающихся друг от друга своими программами. 1.7. Сколько существует неэквивалентных машин Тьюринга в алфавите 10, 1), программы которых содержат только по одной командеу 1.8. По словесному описанию машины Тьюринга построить ее программу (в алфавите 10, 1)).
1) Начав работу с последней единицы массива из единиц, машина «сдвигает» его на одну ячейку влево, не изменяя «остального содержимого» ленты. Головка останавливается на первой единице «перенесенного» массива. 2) Начав двигаться вправо от какой-то «начальной» ячейки, головка «находит» первую при таком перемещении ячейку с единицей (если такая ячейка «встретится на пути») и, сделав «один шаг» вправо, останавливается на соседней ячейке. Если в «начальной» ячейке записана единица, то головка останавливается на соседней справа ячейке. Содержимое ленты не меняется. 3) Машина начинает работу с самой левой непустой ячейки и отыскивает единицу., примыкающую с левой стороны к первому слева массиву из трех нулей («окаймленному» единицами). Головка останавливается на найденной единице (если такая есть).
Содержимое ленты не меняется. 4) При заданном 1 > 1 головка машины, начав работу с произвольной ячейки, содержащей единицу, двигается вправо до тех пор, пока не пройдет подряд ? + 1 нулей. Головка останавливается на первой ячейке за этими 1 + 1 нулями, напечатав в ней 1. Остальное содержимое ленты не меняется. 5) При заданном ? > 1 головка машины, начав работу с какой-то ячейки и двигаясь вправо, ставит подряд 2? единиц и останавливается на последней из них. 6) При заданном 1 > 1 головка машины, двигаясь вправо от какой- либо пустой ячейки, находит первый при таком перемещении массив, содержащий не менее ? единиц, стирает в нем первые 1 единиц и останавливается на самой правой из ячеек, в которых были стертые единицы. Остальное содержимое ленты не меняется. 186 Гл. К Элвмен»пь» теории алгоритмов 2.
Операции над машинами Тьюринга. Пусть машины Т» и Т2 имен>т соответственно программы П» и П2. Предположим, что внутренние алфавиты этих машин не пересекаются и что до -- некоторое заключительное состояние машины Т„а д," какое-либо начальное состояние машины Т2. Заменим всюду в программе П» состояние д' на состояние д" и полученную программу объединим с программой П2. Новая программа П определяет машину Т, называемую комиозииией кашин Т» и Т2 (по паре состояний (д'„, д")) и обозначаемую через Т, оТ2 или Т,Т2 (более подробно: Т = Т(Т», Тз, Щ, д"))).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
