Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 36
Текст из файла (страница 36)
К„,. Пусть машина Тьюринга Т начинает работать в некоторый (начальный) момент времени. Слово, записанное в этот момент на ленте, называется исходным или начальным. Чтобы машина Т действительно начала работать, необходимо поместить считывающую головку против какой-либо ячейки на ленте и указать, в каком состоянии машина Т находится в начальный момент, Если Р, исходное слово,то машина Т,начав работу «на слове» Р„ либо остановится через определенное число шагов, либо ни- ~ д Машины Тьюринга и операции над ними 181 у~Оуз1Л 7~1у10Л у20у3177 уз 1узОЬ д.Оу,ОЛ П: а) Р = 10з1 б) Р = [10)з1.
когда не остановится. В первом случае говорят,что машина Т применима к слову Р, и результатом применения машины Т к слову Р, является слово Р, соответствующее заключительной конфигурации (обозначение Р = Т(Р1)). Во втором случае говорят, что машина Т не применима к слову Р.. В дальнейшем мы будем предполагать, если не оговаривается противное, что: 1) исходное слово непустое, 2) в начальный момент головка находится против самой левой непустой ячейки на.ленте и 3) машина начинает работу, находясь в состоянии дм Зоной работы машины Т (на слове Рз) называется множество всех ячеек, которые за время работы машины хотя бы один раз обозреваются головкой. Часто будет использоваться обозначение [Р[ ' для слов вида РР...Р (т раз), где т > 0; при т = 0 считаем, что [Р['" пустое слово; если Р = а слово длины 1, то вместо аа... а (т раз) и [а]ы будем писать аы. Через И' будем обозначать произвольное конечное слово во внешнем алфавите машины Тьюринга (в частности, пустое, т.
е, состоящее из пустых символов внешнего алфавита). При описании работы машины Тьюринга «на языке конфигураций» будут использоваться выражения, аналогичные такому: уз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е. Элементы теорем алгоритмов Ч,ОЧ,Ы Ч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. Показать, что для всякой машины Тьюринга Т в алфавите А существует счетно-бесконочное множество эквивалентных ей машин Т„рз, ..., Т„„...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
