lekcii4 (Лекции), страница 3

состояния ц, должна быть перенесена из ячейки, содержащей эту букву, в рабочук> ячейку. После того как перенос информации о номере состояния О будет завершен, буква 6,+„должна бьггь заменена буквой а;,. Следовательно., рабочий алфавит машины Т' должен, помимо букв 6, „представлякицих пары (д,,аз,) в текущей рабочей ячейке, содержать еще (р-! 1)(» 1 1) букву 6,'„, т.с. к рабочему алфавиту Лр моделируемой машины Т уже добавлено 2(р -1 1)(в -1 1) букв вида 6,, и 6,, В дальнейтпем буквы 6,, будем,|лля симметрии обозначать 6,,„. Кроме того, введем еще (р 1 1) букву 6,, которые будут указывать, что в данную ячейку будет передаваться информация, но не показывают, с какой стороны. Для того чтобы воспринять букву 6~~, головка должна быть помещена против ячейки, содержащей эту букву. При этом необходимо иметь информацию о том, в какую из соседних ячеек (левую или правую) необходимо перенести номер состояния ц, заменив букву а, записанную в этой ячейке, буквой 6 .

Эта информация может определяться либо состоянием головки машины Т', либо содержимым рабочей ячейки. Состояние 6 означает, что информация будет передаваться палево, а состояние д — направо. Поскольку нашей целью является минимизация числа состояний машины Т', информацию о направлении переноса номера состояния д„, будем хранить на ленте, удвоив число букв 6,,+ и снабдив их еще одним значком, который может принимать значения 1 или г, указывая направление передачи информации о состоянии д„,.

Передача информации о номере состояния д„, из одной ячейки ленты в соседнюю осуществляется машиной Я. Машина,6 переносит эту информацию не за один, а за несколько тактов, причем головка «качается» над ячейками, между которыми передается информация, воспринимая попеременно то одну, то другую ячейку. Отсюда следует, что необходимо также удвоить количество букв 6,, так как, воспринимая одну из букв, головка должна '~Д( получать инф01)маник) О том, Откуда переносится нОмср сОстояния цш (слева или ( П1эава).

Таким образом, рабочий алфавит машины Т' должен содержать все буквы алфавита Л„, (р+ 1) букву вида 6 и еще 4(р + 1)(» 1 1) букв вида 6, „„где т Е (+, — ) показывает, является ли ячейка источником или приемником информации, а = Е 11, т) показывает направление передачи или приема информации о номере состояния. Гак как машины составляются в четверках, они не могут одновременно и сдвигать головку,и заменять букву в рабочей ячейке. Поэтому для каждого типа букв надо будет 67 Выдели'Гь сОстОянис, Отвечаеощсс за движеееие, и сОстОянию, ОтВечающее за записе» ееОВОЙ буквы.

Кроме того, записывая букву 6 в некоторую ячейку, мы ееотеряем информацию о том, с какой стороны мы в нее приепли. Чтобы восстановить эту еееефе>рмацию, машина будет пытаться найти псредакнцую ячейку справа от текущей. Если ей это не удастся, то передаюецуне ячейку необходимо искать слева.

2.4.2.3. 1!остроим машину,5. Эта маепина должна. работать следующим образом, Пусть моделируется такт (2.1) маепины 7", т. е. новой рабочей ячейкой становится правая (левая) соседняя ячейка. Тогда левшина 7' выполняет следующую последовательность действий: 1.3аписьеваст в текУЩсй Ячейке бУквУ 6~„7е „(Ь~„л е), пеРевоДит головкУ в состоЯние Ее, сдвигается направо (ееалево) и записывает в новой рабочей ячейке букву 6 (6 ИЕ~ ЕЕ-Е т' „ т' [Ла,,ат,... а,„, Ь,,„„а,„,... а,,„,) => [Ла,,а,;,... а„, Ь„„, „а,„„. а, „) -= Р ц 7' Ь При движении налево последовательность состояний имеет следующий вид: 7"' 2.Информация о том, с какой стороны находится передающая ячейка, оказывается утерянной.

Т1тобье ее восстановить, машина сдвигает головку вправо и оставляет ее в состоянии р. Команды машины подобраны таким образом, что если справа будет найдена передающая ячейка, то головка вернется назад в состоянии ее. Если же там оказывается обычная ячейка (с буквой а „,, ), то головка вернется назад в состоянии Р. В результате буква в ееринимающей ячейке будет заменена на новую, показывающую, с какой стороны передается информация: ЕФ Р т' т' =~ [Ла,,а,... 6...

Ь „,а,„„...ал„) => [Ла,,а,,... Ьазе,, Ь,,„,а,„,...аь,,) ЕЕ 3.'1сперь можно начать перенос информации о номере, состояния машины путем качаний головки. Во время качаний буквы 6„, „(6 ~~1) заменяются последовательно буквами такого жс вида, но с меньшими значениями первого индекса (номер состояния уменьшается с п1агом 1 до 0). Буквы Ь... (Ьо .), наоборот, заменяются соответствующими буквами Оо,~,,1 Оо„, с большими значениями первого индекса (номер состояния увеличивается с шагом 1).

6 ...,...а,„,) ~ [Ла,,а„...а... 6,„,,„„ р т' Ьо„,, ...а1 ) ~ [Ла11а,, ато,6,„1. „ Р т' 6 ...,...а,„,) =~ [Ла,,а;, а... 6„"„, „ т' => [Ла„а,,...а...Ь, ...а,,;„) ~ =~ «Ла,,ао,... а... 6„..., „Ь, „,,... а,,;„) < т1 [Лан11о2... Ьол . ~ Ь ~1а1 ал ... а1 ) ~ [Лаяа12... 61 ~ Ь~д 1 . 1 а1оо... ал',) Через та таких качаний головки машины Я в старой рабочей ячейке будет содержаться бУква 6,,' „, (Ьо11 1), а в новой Рабочей Ячейке -- бУква Ь„'„., (Ь,„л,), т. е.

инфоРмациз1 о номере состояния будет перенесена в новую рабочу1о ячейку. Останется лишь заменить букву 6,+,, (Ьо,,) буквой а „и перейти в новую рабочую ячейку в состоянии, означающем О,.ь,т Ось1 что ка,чания завершит1ись. т' а„„,) =>' [Ла,а,...а,,а., 6„", 1 ...а,.„,) [Ла,,,...,... Ь„',:, „6 а т' а, „,) =>' [Ла,,а „... Ь„„, „а,а,„„...

а, „,) р Таким образом, работа машины .5' определяется слелунлцей таблицей: состояние 1 состояние р состояние д новое новое новое со- стоя- стоя- стоя- ние пие ние Ь' о, 6,„. 0>1) а.; Ц=1) Ь... 1'-~-1 1,1 зависит от команды моделируемой ма1пи- НЬ1 14-1 он зависит от команды моделируемой маши- ны Буква в рабочей ячейке записываемая буква или действие записываема,я буква или действие записываемая буква или действие Работа машины Т' теперь может быть описана следующим образом. Начальной конфигурации ~ а = [Лпз пз ° аз' "- ) ~~о машины 7' сопоставим конфигурацию (2.3) машины Т'.

Каждой команде машины Т вида (щ, а„г. ц„,) или (д, а,, 1, д ) поставим В соогьетсгвис пару команд мапшпы Т (7,6;энь- „. 7), (р,ь;,„,ь,„, 7) и (р, Ь,,: „, Ь,„, „, д) . (ц, 6, „, .6+ „, д) (2.4) соответственно. Какая именно из двух команд будет выполнена, определяется предыдущим тактом машины.

Каждая из команд (2.:1) запускает машину Я, которая за, т качаний реализует последовательность тактов (2.2), моделирующую такт (2.1). Командам машины Т с неподвижной головкой соответствуют пары команд машины 7": команде (д,;, а, ап д„„) соответствуют команды (р, 6,„, Ь„,~,„р) и (ц, ь.,н ь,„~н д). Легко видеть, что заключительная конфигурация машины Т' будет отличаться от заключительной конфигурации машины Т только тем, что в рабочей ячейке будет записана буква вида 6, . соответствующая заключительной паре (о„а.;) машины Т. Таким образом, машина Т' действительно имеет всего три состояния и моделирует машину Т.

'1еорема 2А.1 доказана. П Машину Шеннона В можно описать через диаграмму. Для этого разобьем команды исходной машины на три вида: 1. Команды с подвижной головкой„т. е. команды вида (Ц,, и, ан г, Ц,„) и (7,„п„аь 1, и„,,). Им будут соответствовать машины В, == 6+ В, и В, = 6,Я описываемые следующими диаграммами: В этих диаграммах были использованы вспомогательные машины, которьк.

также следует описать. Машины 1 и 0 выполняют инкремент и дскремент увеличивают или уменьшают значение правого индекса оуквы в рабочей ячейке. ~2оьо Машины ЛХ, и ЛХ~ помечают ту ячейку, в которую на данном шаге будет передаваться информация, и возвращают головку назад. ао ЛО,О„ ао ~'о.о,~ Лсл,. Наконец, машины Л восстанавливает в рабочей .ячейке знак из алфавита, машины 'Г. ооуо по п1 Всюду здесь стрелки, помеченные оуквами вида бра, являются на самом деле семей- ствами стрелок по одной для каждого р = О, 1,..., ~ и д = О, 1,..., в. но т. к.

переход по любой из таких стрелок 1оавнозна ген с точки зрения выполняемых дальше дей- ствий, он были обьединены в одну 1ля наглядности. 2. Командам с неподвижной головкой (о„ао, аь я, д ) соответствуют машины 3. Терминальные команды машины Т (командь> вида (фг а>ч а>, >гг ф)) предславляют собой особый случай, и им не ставятся в соответствие никакие ма>нины. Теис рь можно составить диаграмму манлины гЯ: Под Ь;:р здесь подразумеваются все такие буквы алфавита машины Я, что пара (ц„а ) определяет терминальную команду машины '!' (именно поэтому им не была поставлена в соответствие никакая машина). Остальные оуквы отмечены как г>, Ма>пина л', определяемая полученной диаграммой, моделирует машину Шеннона (достаточно сравнить способы их построения), а следовательно, и исходнук> машину Т.

За.>иечание. Сама по себе диаграмма не может являться доказательством теоремы, т. к. из нее не следует, что описываемая ей машина может иметь всего два состояния, но она служит хорошей иллк>страцией работы машины Шеннона, построенной в доказательстве. Замечание. Диаграмма машины Я является схемой. Это легко видеть, т. к. структурнымлл являются мал>ивы 1, О, Мь М„1лг Я, Ь, и, соответственно, машины В;:.

Структурность машины Я отражает структурность алгоритма, с помощьк> которого мы строили эту машину. Его можно описать так: пока не встречена буква„соответствующая терминальной команде, моделировать следующий такт машины Т (соответствует внешнему циклу на диаграмме З). Описание моделирования отдельного такта (за исключением подготовительных и завершающих действий) тоже»циклично»: пока первый индекс буквы в передак>щей ячейке не равен нулю, увеличить первый индекс буквы в принимающей ячейке и уменьшить первый индекс буквы в глередающей ячейке на 1. Лекция 9 2,4.4 Доказательство теоремы 2.4.2 Применим диаграммы Тьюринга к доказательству второй теоремы Шешюпа. Для доказательства теорехлы 2А.2 необходимо построить машину Тд с рабочим алфа; витом Ад —— ~)), моделирулощую работу машины Т с рабочим алфавитом Ар (р > 1).

Сначала установим соответствие между конфигурацией исхс>дной машины Т и моделируюлцей машины Ть Кодирование букв алфавита Ар над алфавитом Ад будем производить способом, Указанным в УтвеРждении 1А.1: в качестве кода бУквы а Е Ар(1 = Ог1,...,Р) будем брать слово а' = ас ада>... ал Е А*,, Для наглялности будеъл обозначать ас через Л, 1 а букву а,> через )г так что а,' = Л !!... !. Ситуации машины Т [Ла,,а,,... а...(а»»)а»»„,... а»„,Л > >-1 , а Е Ар, ! = лл, 1аг...,! поставим в соответствие слсдУющУк> ситУацию машины '1>. [ЛЛ[Л [)...

! Л )[... [... Л й... )(Л) [й... ! Л [)... )... Л !)... [ Л)Л > ггл-1 гч. > гь г»Л гг-~-> г», г»-Л г.,-'1 Соотв<.тстви<. мех<1<у ситув пнями позвог<яет установись и соотвст<г< вие »<ежду «онфигурапиями. Диаграмму машины Т< получим из диаграммы исходной машины Т следующих< образом. Сначала приведем диаграмму машины Т к виду, в котором она содержит только символы элементарных машин (такое преобразование уже рассматривалось при доказательстве теоремы 2А,2). В полу <енной диаграмме заменим символы эл<'ментарных ма<лип г,1, аь Л (1 = 1,2,...,р) и стрелки диаграммами машин Л1„, И<. Л1„,, Им Л1 с таким расчетом, чтобы полученная диаграмма описывала машину, модслируклцую исходнук> машину Т.

Перейдем к построению машин ЛХ„Л1<, Л1„,, Л1 и Л1м Машина ЛХ,. должна моделировать работу элементарной машины г„которая, как известно,переводит ситуацию в ситуацию Следовательно, машина М, должна осуществлять такую последовательность тактов: =~* [Ла,,', а,,',... а'„, Л [[... [(Л) [[... [... а', Л > <«<»1 Таким образом, диаграмма машины М„.