lekcii4 (Лекции)

еш — > ~е е> — » Как видно из этого примера, даже для относительно простой задачи составление НАМ оказывается весьма трудным делом, к тому же корректность такой системы вовсе неочевидна [20~. Алгоритмическая модель Маркова лежит в основе весьма интересного отечественного языка программирования рекурсивных функций РЕФАЛ, предложенного еще в 1966 году профессором Турчиным В. Ф. ~81].

(Некоторая информация о РЕФАЛе находится на хрестоматийном диске.) Кроме того, развитые средства текстового поиска и замен ядро НАМ хорошо реализованы в современных интерпретируемых командных языках Рег!> Ру1,1>оп, РНР и в библиотеке ВТЬ. 2.4 Исследование алгоритмической модели Тьюринга 2.4. 1 Теоремы Шеннона Теоремы Шеннона позволяют выяснить, какой смысл имеют состояния головки ма>пины Тьюринга.

Из этих теорем следует, .что состояния головки — это вид пахляти, причем сели у машины Тьюринга много состояний., то их число можно уменьшить, увсличив соответственно число букв рабочего алфавита. Теорема 2.4.1. Для любой машины Тьюринга Т = (Ав, Я, Р, >>с) с множеством состояний О = ~ца> >>>, ..., >>,) можно эффективным образом построить машину Тьюринга Т' = (А„1с>, р), Р', ©, моделирующую машину Т и имеющую всего два состояния: с> и Д. Рабочий алфавит А„, машины Т' содержит г = 3(р+ 1)(в + 1) + р букв.

Теорема 2.4.2. Для любой машины Тьюринга Т = (А„, Я, Р, д>>) можно эффективным образом построить машину Тьюринга Т" = (А>, Я", Р", >>аа), моделируюшую машину Т и имеющую однобуквенный рабочий алфавит А> — — 1а> ) = ~/). Произведение (р+ 1) (в + 1) является одной из характеристик эффективности алгоритма, описываемого МТ: алгоритм тем эффективнее, чем меньше значение произведения (р + 1)(а + 1). Следовательно, >иашины Т' и Т" из теорекл 2.4.1 и 2.4.2 опреде>п>ют менее эфс1>ективные алгоритмы, чем моделируемая машина 7'. Отметим также, что алгоритмы, определяемые указанными машинами 7" и Т" > выполняются за болыцее число тактов., чем алгоритм, определяемый исходной машиной Т (это следует из определения 2.2.5). Доказательство теорем Шеннона следует броппоре ~4].

В частности, первая теорема сначала доказывается в авторской редакции в терминах пятерок. СВязь ме>жду четВерками и пятерками ЛОВОльнО прост>>: (д,а.,а. >В,~~) > (д,а,а,д ),(г1,а,г>>д) (д,а,»,ц) (>1,а,,»,в,>1) или (>1,а,.а,.4>,.д) Вообще, для любой МТ Т4 в пятерках с 1 состояниями >1ш д>,..., О>, > можно эф4>ективным образом построить ълоделирующую ее машину Т> в четверках с числом состояний 314 и с тем же рабочим алфавитом: для каждого состояния д, машины 1';, введем два дополнительных состоЯниЯ машины 74 Щ ь >1> „.

ДлЯ кажДой команДы (Ц;, а, а', >>, >1>) машины Те с подвижной головкой внесем в программу машины Т4 команду (>1„п, »>, д „). Кроме того, 60 дополним программу мап>ины 7л командами вида (щ,„, х, », щ) для всех ? Е 10,...., >з — 1), и Е 11, г), >г Е Ар (Ар алфавит машины 7;;. Выполнение команд машины 7> разбивается на два такта: на первом такте в рабочую ячейку записывается нужная буква, а на втором происходит сдвиг и переход в конечное состояние; при этом информация о направлении сдвига и конечном состоянии хранится в промежуточном состоянии цз „.

Залаечание. Напишите программу на Паскале или на Си, транслирун>п>ун> четверки в пятерки и наоборот! Дополнительнук> ин>1>ормацин> о м>янинах Тьк>ринга>, с малым числом состояний можно почерпнуть из работы Шеннона ~18~ и в сборнике ~7~. В частности, там говорится о невозможности построить машину только с одним состоянием. В связи с этим вспомните ранее приведенные примеры неостанавливающихся машин.

Зимечание. Доказательства этих теорем были предложены величайшим ученым в области информатики и кибернетики Клодом Шенноном в 1956 году. В 2005 году студентом МЛИ Рисенбергом Д. В. результат первой теоремы был усилен и количество вспомогательных букв было сокращено с 4(р+ 1) (в+1) +р до 3(р+ 1)(а+ 1)+р благодаря оригинальному способу моделирования возврата головки МТ в исходную ячейку команды. Кроме того, им же было получено доказательство первой теоремы Шеннона для машин Тьюринга со специализированными командами, приводимое далее, и его диаграммная иллюстрация, полученная методом нисходящего проектирования.

Замечание. ( Теоремы Шеннона в переложении для фор»>впиаио). 'Теоремы Шеннона обосновывают трансформаци>о (перекодироваиие) л>обых алгоритмов либо к меньшему числу состояний (этапов, стадий, в некотором смысле меток) ценой существенного увеличения рабочего алфавита, либо к очень бедному (но зато технически реализуемомуГ) алфавиту. Существуют некоторые простые соображения в пользу этих теорем, аналогичные кодированию любого алфавита словами из палочек. Так, известной всем морзянкой из двух собственных букв (точка, тире) и одной несобственной (пауза) можно передавать нс толысо текстовыс сообщения, но и изображения (фототелеграф), и даже закодированные аудио- и видеоданные.

Голосовая связь в то время из-за несовершенства, аппаратуры и линий связи была невозможна, 13>олег соврсменный пример; импульсная и тоновая коммутация абонентс>в телефонной сети, 1!ри импульсной коммутации помер 123-15-67 набирается как последовательность слов ! 1! Ш Ш! ШШ ШШ ШШ! длины 34, а при тоновой -- как последовательность аудиобукв, представляемых разноча- стотными звуками Ьоо >0.)>оо У»оо Ж У7оо Упоо "Ьоо Лзоо С>,6оо азов 0> Ьоо Лзоо 6З Упоо Лзоо ~Э У7оо. существенно меньшей длины (13). Налицо удобство тоновой системы. Но гючему же она пе применялась в нашей стране'? Ответ следует из второй теоремы Шеннона: обогащение алфавита недопустимо по тем временам усложнило бы абонентскую и коммутационную аппаратуру. Кстати, настоящий импульсный телефон вместо наборного диска, должен иметь лишь одну кнопку.

Кнопка для паузы может отсутствовать как на телеграфном ключе. Теоремы Шеннона также дают обоснование правомерности запрета использования дополнительных букв при программировании машин Тьюринга, поскольку всякая лишняя буква может быль дезавуирована несколькими лополнительными состояниями. Вторая теорема Шеннона была применена на практике задолго до сво>то дс>казательства: Джон фон Нейман прелложил использовать двоичнук> систему счисления в конструкции компьн>герон не только для представлония данных,но и для записи программ.

2.4.2 Доказательство 1 теоремы Шеннона (К. Шеннон,1956) 0 2.4.2.1. Рассмотрим какую-нибудь конфигурацию ма>пины Т: Команда машины Т, которая должна быть гтрименена в конфигурации С, опреде;жется состоянием головки д; и буквой а.„, воспринимаемой головкой. 1Лз ог>ределения 2.1.1 следует, что если машина Т' моделирует машину Т, то среди конфигураций машины Т' должна содержаться конфигурация С', являющаяся образом конфигурации С и содержащая в закодированном виде информацию о наре (д,, а „), определяющую работу моделируемой машины. Но у машины Т' всего два состояния: следовательно, в конфигурации С' головка машины Т' может находиться в одном из состояний о или >>', воспринимая букву и' е А,. При этом информация о паре (д;, а>,) может содержаться только в букве а'. Для того чтобы это было возможно, добавим к алфавиту А„машины Т (1э+ 1)(в 1 1) букв а,', каждая из которых представляет собой одну из пар (д, а>,).

Для удобства, примем для буквы а', представляющей пару (ц,> а>,), обозначение а' = 6,, В ка >ествс образа конфигурации возьмем конфигурацию С'= (Ла„п,;,,...и,, 6, „а,,...а.„Л) а Конфигурация С' отличается от конфигурации С лишь состоянием и содержимым ячейки, воспринимаемой головкой: буква, записанная в этой ячейке, содержит информацию о паре (д;, а,,). 2.4.2.2.

Рассмотрим какой-нибудь такт машины Т. Имеем т Ла,>о,„...а.. > и, а,,,...а>„Л) ==; ~Ла»аэ>...а;, >и>„, и>,, ...п>хЛ) (21) Чг Ч»> Согласно определению 2.1.1, такту 2.1 машины Т должна соответствовать такая последовательность тактов моделирующей машины Т'. т' (Лп>>п> .. а>-->6',>~а>г,> .. а,„Л) ===~' (Лп> .. пэи->и>, 6~»г . я,„Л) (2.2) Но замена, буквы в рабочей ячейке производится до перемещения головки, откуда, следует, что если в конфигурации С' мы заменим 6;, „, на, а...

то будет утеряна информация о номере следующего состояния д . Следовательно, информация о номере д должна быть сначала помещена в рабочук> ячейку конфигурации С', а потом перенесена в новую рабочую ячейку, т, с, последовательность конфигураций 2.2 должна иметь вид т, т ~Лая... о>», 6;, > пз»,,... о, „Л) =~ ~а,...а>»,6„, и,, ...и „Л) =»* [Лпяп» пи,п „6-З...