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