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