Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 35
Текст из файла (страница 35)
.у(») = х1(») -+ хг(»), » > 1о Гг задается диаграммой Мура, изображенной на рис. 4.67, а о(ц '(') цо) о 0(0) а 0 * 1 1ЦЦ ОЦО) 10(1) б оо(о) 10(0 ' 1цц 10(ц 0 *Оо(Ц,ОЦ1 ОЦ1) 1цц Рис. 4.67 6) 71. .у(») = х1(») хг(»), » > 1, »2 задается диаграммой Мура, изображенной на рис. 4.67, б; 9) 11. у(») = х1(»)оо'хг(»), » > 1, 52 задается диаграммой Мура, изображенной на рис. 4.67, в: 10) 11. .у(») = х1(») — 1 хг(»), » ) 1, у1(») = х1(») * (») 1»Ч(» — 1), у2(») хг(»)' Ч(» 1)о Ч (») — Х2 (») о Ч(о) =О:, 176 Гж 11', Ограниченно-денгернинированные функции 11) 71.. У(1) = У(1), е > 1, У1(З) = х1 (З) Уг(З) В хз(1) Е Ч(4 — 1), уг(З) = х (З) Е Ч(З вЂ” 1), Ч(З) = х (1) ц(0) = 0,: 12) 21.
У(1) = хг(1) хг(й), У > 1, уг(З) = х1(З) Уг(З) У ц(З вЂ” 1),. Уг(е) х1(е) " Ч(з 1) Ь: Ч(З) = х1(Е), Ч(О) = О; 13) (1. .У(з) =Уз(1).У2(г), 1 > 1, у(е) = х1 (1) ' Ч1(Х вЂ” 1) У х2(з) ' Ч2(е — 1), Ч1(З) х1(З)' Ч1(1 1) ч хг(З) Ь Ч2(З) — * (З) ' Ч1(е 1) ч Ч2(1 1) Ч1(0) = цг(0) = 0; 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ! ~ ~ ! ! ~ ~ 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ! у(У) = ц(С вЂ” 1), у(1) = У1(1) ч' хг(1)Ч Уз(1) ' Ч(1 14) у ц(З) = У(З), у ц(З) = У1(З)1ухз(З), Ц(О) = О, Ч(О) = О; у(Ю) = ц(1 — 1), у(з) = хд(з)1гхг(з) ц($ 16) Л: ц(У) =: (1) Чз 2(1) Ь: ц(1) =Ч(1 — 1) ц(О) = О, ц(О) = 1. — 1), — 1), 2.18. Доказать, что функция г является шефферовой в Рг относительно множества операций Сг = (01, 02, Оз, О~О Я); у(1) = У1(1)Ч У2Я 11Уз(з) ° Ч(1 — 1), 1) 7: Ч(1) = Уз(1).У1(1), ц(о) = о; у(З) = У1(З) ° хг(З)дУз(И) Ч(З вЂ” 1), 2) г': Ч(З) = х1(З) 1 (хг(С) -2 хз(С)), Ч(0) = 1; у(З) = т1(1) уг(И) хз(З)12Ч(1 — 1), 3) 1: Ч(4) = х1(з).
хг(з), Ч(О) = О; У(1) = У1(З) 'хг (1) У Ц1 (е — 1) ' Чг (е — 1), 4) 7": Ч1(1) = хг(1) Уз(З), Чг(1) = хг(З) хз(С) ~/Ч1(Š— 1), ц(0) = О, цг(0) = 1; 2" х. 27ииграммы, иуаолииы, канонические уравнения, схемы 177 уг(1) = х1(1) уг(2- 1), Уз(у) = х1(Г)' дг(у 1) у хз(у) ' чз(у — 1), д~(2) = х1(у) хз(1), Ч2 (е) Ч1 (1 1) д,(О) = дз(О) = О.
5) Х: 12 Г. П. Гаврилов, А. А. Сапожонка 2.19. Из системы А, полной в Рз,„относительно множества операций (01, 02, Оз, 04, Я), выделить собственную подсистему, полную в Рз, относительно тех же операций (и состоящую из возможно меньшего числа функций); 1) А = <Х= (х) Хи (х): Х' (х у): Ххэ е1к(х у 2) 1ру(х))' 2) А = (Хио(х), Х, у(х, у), Х, у(х, у), 1рз(Хи(х))); 3) А = (Х=г(х), Ххоуу(х, у), Ххоу(х, у), 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 = 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 ~ —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
