Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 37
Текст из файла (страница 37)
Машины Тьюринга Т, и Тз называются эквивалентными (в алфавите А), если для всякого входного слова Р (в алфавите А) выполняется соотношение Тг(Р) = Тз(Р), означающее следующее: результаты Тз(Р) и Тз(Р) определены или не определены одновременно (т.е. машины Тз и Тз либо обе применимы, либо обе не применимы к слову Р) и, если зти результаты определены, Т,(Р) = Тз(Р). Символ = называется знаком условного равентпви Пример 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е. Элементы теорем алгоритмов Ч,ОЧ,Ы Ч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)м (и, > Ц; 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' 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
