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

пл.Л) а В последнем соотношении звездочкой (*) обозначено одно из двух состояний машины Т' (далее будет уточнено, какое именно). Символом 6,», обозначена еще одна дополнительная буква рабочего алфавита, машины Т' (опа отличается от буквы 6„...). Буква 6,;, находится в ячейке, соседней с новой рабочей, и показывает, что информапия о номере т, состояния д,„, должна, быть перенесена из ячейки, содержащей эту букву, в рабочую ячейку. Г!осле того как перенос информапии о номере состояния д„, будет завершен, буква 6+ должна быть заменена буквой а,, Следовательно, рабочий алфавит машины Т' должен помимо букв 6,,„, представляющих пары (д.;, а») в текущей рабочей ячейке, содержать еще (р 61)(» 1 1) букву 6,,, т.

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

Эта информация может определяет состояние головки машины Т~. Состояние >> означает, что информация о состоянии головки будет передаваться налево, а состояние а - направо. Передача информации о помере состояния д„, из одной ячейки ленты в соседнюю осуществляется машиной >', построенной Шеппопом в ходе доказательства рассматриваемой теоремы. Машина .Я переносит эту информацию не за один, а за несколько тактов, причем головка «качается» над ячейками, между которыми передается информация, воспринимая попеременно то одну, то другую ячейку.

Таким образом, рабочий алфавит машины Т' должен содержать все буквы алфавита, А„и еще (р > 1)(а 1- 1) букв вида 6,", и 2(р + 1)(в + 1) букв вида 6,, где, >л Е 11, г) показывает местоположение источника информации. 2.4.2.3. Построим машину Шеннона >. Эта машина должна работать следуютцим образом.

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

Если бы информация передавалась налево, то после записи буквы 6',, в старую рабочун> Состояние о Состояние ~3 Буква в рабочей ячейке Записываемая буква Записываемая буква Новое состояние Действие Новое состоя нис Действие !о, Зависи Ьо. ! !»! г! 61-~-1 гзг 6,+,, а; а, 6... 6,,(1 > О) Ьо; т от команды моделируемой мьнпины 6,+ „ а, г Работа машины Т' теперь может быть описана следующим образом. Начальной конфигурации Со= Ра!газ, а!т, ц» а!»„..а, ) г7о машины Т согюставим конфигурацию С' = (Ла,,аз2...

а,ь, Ьо„.„. а,„,... а,„,... Л) (2.3) машины Т' (значение х может быть любым, так как все равно буква 6, будет сразу же заменена одной из букв 6, з), Каждой команде машины Т !лида. (д1, а,, а1, г, г7„,) или (г7,, а»ч а1,1, г7„,) поставим в соответствие команды машины Т' (а,6,,„6 „г, !3) и (а,.6,,„6„'„,,1,о,) (2.4) соответственно, где х пробегает множество (1, г).

Не рассмотренные выше команды с неподвижной головкой моделируются непосредственно без качаний: команде (д„а,а1, з,11 ) машины Т поставим в соответствие команду (!7,6,, Ь,„,, «, !1) ма!пины 7". Каждая из команд (2.4) «запускает» машину Шеннона,5', которая за т качаний реализует последовательность тактов (2.2), моделирующую такт (2.1). Легко видеть, что заклн1чительная ячейку головка была бы перемещена налево и оставлена в состоянии г1. В новую рабочу1о ячейку была бы записана буква Ьо „. после чего головка была бы сдвинута направо, о.7» ° 1 г' в старую рабочую ячейку, и оставлена в состоянии /3. Во время «качаний» буквы 6, заменяются последовательно буквами такого же вида, .но с меныпими значениями первого индекса (номер состояния уменыпается с шагом 1 до О).

Буквы 61, „наоборот, заменя- !!,З»г ь1' !отея сгзответствующими буквами с большими значениями первого индекса (номер состо- яния увеличивается с шагом 1). Через т таких «качаний» головки машины Я в старой рабочей ячейке будет содержаться буква 6,",, а в новой рабочей ячейке буква 6,„, т. с.

информация о номере состояния будет перенесена в новую рабочую ячейку и оста- нется лишь заменить букву 6„+, буквой а,, Таким образом, работа мап1ины Я определяется следующей таблицей: конфигурация машины Т' будет отличаться от заключительной конфи| урации машины Т только тем, что в рабочей ячейке будет записана буква вида Ь,„соответствук0щая заключительной паре (д7, а,) машины Т.

Таким образом, мангина Т' действительно имеет всего два состояния и моделирует машину Т. Теорема доказана. П Зи54ечан44е. Рассмотрим пример моделирования такта классической машиной Шеннона Я. Пусть в некоторый момент времени моделируемая машина должна выполнить команду (535, а5, а7, 26 02), где в = (1, т~. В терминах машины Ь это озна тает, что в текущей ячейке содержится буква 6,, „., (индекс т для нас не важен, поскольку он принимает одно из двух значений (7, г~ и озна, тает, с какой стороны головка подслпла, к этой ячейке).

Машина Я находится в состоянии сс Работу этой машины нам поможет проследить следующая диаграмма: и П7 Из этой диаграммы видно, .что при переносе информации о состоянии используется лишь одно состояние машины Я, а именно ~3. Только вначале используется состояние 72 для того, чтобы перенести в соседнюю ячейку информацию о том, откуда приехала головка, т. е. машина Я содержит резерв, который может быть использован в целях оптимизации.

Так, можно отказаться от букв вида Ь,, заменив их буквами вида Ь,:, а информацию о положении целевой ячейки сохранять при помощи состояний машины,5': например, д указывает, что головка моделируемой машины должна переместиться налево, а о -- направо. Теперь перепи5псм пример для новой машины Я'. Диаграмма из примера примет вид: 65 О 5.5,х д 4 Ь..ь Ь. ~3 22,0, Я Р 6 '3 22,ЬЛ 7,0,П, 22,2,Л б..ь, 4 624 64 д 24,0,5 3 6 6+ '3 7пл > 24Л,Ь 6 7,0,В 24,2,5 а7 2.4.3 Доказательство 1 теоремы Шеннона (Д. Рисенберг, 2005) г> 2.4.2.1.

Рассмотрим какую-нибудь конфигурацию машины Т: С (Лц п3 ' ' ' сэ юз яг ' В3 с1г Команда машины Т, которая должна быть применена в конфигурации С, определяется состсьчнием головки сь и буквой а, г воспринимаемой головкой. Из опредсгления 2.2.5 следует., что если машина 7" моделирует маслину Т, то среди конфигураций машины 7' должна содержаться конфигурация С', являющаяся образом конфигурации С и содержа- щаЯ в закодиРованном виде инфоРмацию о паРе (сй, а,) г так как эта инфоРмациЯ опРеделяет работу моделируемой машины.

Но у машины Т' всего три состояния; следовательно, в конфигурации бк головка машины 7" может находиться в одном из состояний р, с7 или А, воспринимая букву а Е А„. При этом информация о паре (с1,, а „) может содержаться только в букве а'. Для того чтобы это было возможно, добавим к алфавиту Ар машины Т (р+ 1)(я + 1) букв а,', каждая из которых представляет собой одну из пар (д;, а „). Для удобства примем для буквы а,', представляющей пару (д;, а,), обозначение а' = 6,, В качестве образа конфигурации возьмем конфигурацию С' = (Лалаэг... оэ,, 6, „асг,,...п.„Л) с1 КонфигУРации С' отличается от конфигУРапии С лиспь состоянием и содс,1~жимым Ягсейкиг воспринимаемой головкой: буква,, записанная в этой ячейке, содержит информацию о паре (д;, а,,).

2.4.2.2. Рассмотрим какой-нибудь такт машины Т. Имеем т (Ла,са,,... ц„, а,„а,„., а Л) =~ (Лсс,га,,...а,„,а,:„а,,„,,г ...а„,) Сгг Чг~ Согласно определению 2.2.5, такту 2.1 машины Т должна соответствовать следующая послсдовательностс тактов моделирующей магнины Т'. т' (2.2) а а 5,.г г„.г3 гг Ь,, 6,0 22,Сг,гс О г,, 6 гь 6зккл ггг гг о 2с огь 6 О' 24.кь 6 624д,с, По если с1зазу пе1земесгить 1юловку в новук) ячейку.

,го б1де г 1теряна инфо1змация о номере следующего состояния и,„. Следователык>, информация о номере д,„должна быть сначала помещена, в рабочую ячейку конфигурации С', а потом перенесена в новую рабочую ячейку, т. е. последовательность конфигураций 2.2 должна иметь вид тР Т' [Лпв ц; Й~„, п~:,, 6~в~„1 06, Л) В последнем соотношении звездочкой (~) обозначено состояние р или д машины Т' (далее будет уточнено, какое именно). Символом 6 обозначена еще одна дополнительная буква рабочего алфавита машины Т' (она отличается от буквы 6„,,). Ьуква 6", „находится в ячейке, соседней с новой рабочей, и показывает, что информация о помере т.