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