1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (Котов, Сабельфельд 1991 - Теория схем программ), страница 4

1.4. Пример машины Тьюринга. Пусть алфавит У состоит из двух символов — открывающей и закрывающей скобок: У = = ((,)). Выделим во множестве Р» подмножество М»правильныхэ слов, которые определим следующим образом: 1) пустое слово е ~ М; 2) если а принадлежит М, то слова ( ) а, а ( ) и (а) также принадлежат М. Построим машину Тьюринга, на ленту которой подаются слова из 'г'», и машина узнает, принадлежит данное слово множеству М или нет. Для этого машина должна остановиться с односимвольным словом 1 на ленте, если начальное слово принадлежит М, и с результатом Π— в противном случае.

Другими словами, машина Тьюринга должна задавать предикат Р: У» -~ (О, 1) такой, что ( 1, если аЕ-"М, ( О, если а~М. Алфавит машины включает, кроме скобок, символы О, 1 и», Искомая машина Тьюринга имеет следующий вид (для простоты отождествим машину Т с ее описанием): Т ((() О $ «) (дз дз дз дз Д4) дз Ф 1) где программа 1 содержит следующие команды (перенумерованные для последующих ссылок): 4 д( дз(г. 2 д,) д «4- 3. Дзз'-1дз«1' 4- Д44~-+Д44~(. 5. Д1 (-+ дз «г.

6. Д1 «- д1 «4. 7. Д44~ дзог 8 Дз( дз4ь(. 9. д « - дзф'1. 1О. д, др-~ дз1 р. 11. д (-зд дую. 12. д «- д ~ф 4. 13. Дзф- д Ор. 14 д (- Д4~г. 15 дз) дзФг 16 Д4'з дзф~г Когда машина находится в состоянии дз, головка движется направо в поиске первой слева закрывающей скобки. Найдя зту скобку, ояа замещает ее звездочкой я возвращается назад з новом состоянии д, в котором нщет парную открывающую скобку. Встретив ее, вновь возвращается назад в состояние дз и движется направо, и т. д. Если головка достигнет левого символа ~, она записывает символ О (не нашлось парной открывааяцей скобки) и переходит в состояние дз, находясь в котором движется направо, стирая все символы. Если же головка достигнет правого символа ~, она переходит в состояние дз и возвращается к началу слова, стирая по пути символы. Если она вернется к началу слова, не встретив по пути открывающей скобки (заданное слово — правильное), она запшпет 1, и машина остановится.

Если же встретится хотя бы одна открывающая скобка (слово неправилъное), машина перейдет в состояние дз, которое заставит головку записать О в начале слова и остановиться. Функционирование машины Тъюршпа можно описать с помощью протокола работы над заданным начальным словом. Пусть ®озоз...оз заз...а„-к- — слово, возникающее на ленте в процессе работы машины после некоторого шага, в результате которого мавшна находится в состоянин д, а головка обозревает клетку„ содержащую Й-й слева символ слова. Слово фазаз...аз 1даз...а„~ называется кон(бязурацигй лапяины Тьюринга.

Последовательность конфигураций, выписанных в том порядке, в котором они следуют в процессе работы машины, н нааывается ярошо- ЮМОМ. Так протокол работы рассматриваемой машины Тьюринга над словом (( )( ) имеет следующий вид (между конфигурациями выписаны номера выполняемых команд): В дзИ )()Ж $ Головка перемещается каправо, игнорируя дд(дз( Х )др открывающие скобки. Ы 4 Ж ((Да)( Н~ 2 Обнаружена закрывающая скобка, которая ф (д (е( )~ф езачеркивается» символом е.

5 Головка возвращается обратно и наводит ~'(адаа( )ф парную открывающую скобку„которую аачеркввает. 3 Головка вновь движется вправо в понске закрывающей скобки. 1И( ба(НР $ чр ( (ба)Ж 2 Закрывающая скобка обнаружена. Ф( АЖ" 5 Обнаружена парная открывающая скобка. Ф(*аа Ж 3 Снова движение направо. Ф(аа ЬЖ 4 Головка дотла до конца слова. ф (ваедаа~ 9 4~' (е ЮааЖ4~ 9 Головка движется влево в поиске лишней открывающей скобки нлн начала слова, стирая на пути звездочки.

4~ (ебаЧИЙК' 9 Ж (ра ФИНА 9 4К' та И~Ф4ЙВЖ 8 Обнаружена лившяя открывающая скобка, которая стирается. Ф %4$Ж4ИЙИР $3 Обнаружено начало слова, и записывается О. 1И 9.91ИЦЩ Машина останавливается, так вак ни одна из команд ее программы не применима. Результат работы построенной машины Тьюринга показывает, что слово (()() не является правильным.

Задание а.з. А. Псстрсйта маювау Тьвувага, кстераа сшрает с завам юобае зачала аеа саеао и ааааамваат вместе ваге свозе ааааа а аафаееае (а, 6). Б. Пеатуевта маюаау Тьюрюпа, вставая любое аадавасе слово аааа... ...е„а аафаеата (О, 1) ауеебуаауат е авеуааауауаеаэ стезе е„... е,аа. 1.5. Саеварнее представление машины Тьюринга. Машина Тьюринга однозначно еадастся своей программой. Если упорядочить ее команды произвольным образом и применить окисзпнмй ниже способ кодировки последовательности команд словом аб алфавите машины «'ьюрннга, то можно получить ее описание „:н собственном алфавите. Пусть У вЂ” алфавит машины Тьюринга Т, а (~ — множество гее состояний. Упорядочвм некоторым образом множество 'и пусть К (о) — порядковый номер состояния д.

Введем вспомоогательный символ», не входящий в У, и сопоставим каждой ко"манде до-»д'о'И слово в алфавите гт = У () Щ, г, г, р, ») следующего вида: »к<«)о»хг«ча'гг. ' Упорядоченной последовательности команд соответствует после' довательность слов в алфавите $т. Результатом конкатенацви З является елово аг, однозначно описывающее машину Т (с точ:,:.

ностью до наименований состояний). Следующий этап кодировки— 1: переход от представленвя машины в алфавите Ю к представлению ~ в алфавите У. Если алфавит У содержит и символов, то, упорядо:, чив его каким-либо образом (для кодировки слов из У» числами), (( упорядочнм алфавит Иг так, чтобы дополнительные символы, не ) входящие в Г, получили следующие номера: К' (ф) = я+ $, ( К' (») = п + 2, К' (г) = и + 3, К' (г) = п + 4, К' (р) = и + 5. Закодировав слова иэ г» и «г"» числами описанным в разде' ле 1.2 способом, узнав яомер слова гэт нз $уъ и выбрав слово из У» , с тем же номером, найдем словарное предсгкевлснис (гг з«ашиим ! Тьюринга Т в ее алфавите.

По слову )гг можно однозначно (с точ( ностью до наименования состояний) восстановить программу ма- ~' шины Т. Заметнм, что одной и той же машине Тьюринга соответст;,: вуют различные словарные представления в ее алфавите в зави' симости от выбора упорядочений множеств Д, У, г, но по любюму . иэ этих представлений программа машины восстанавливается однозначно. й 2. Разрешимые и неразрешимые проблемы 2 1.

Маесевые алгеритмичееиие проблемы. Изучая свойства . программ и их математических абстракций — схем программ, мы ' имеем дело с так нааываеммми массовыми алгоритмическимн ,' проблемамн. Конечная цель теории схем — автоматизация про', граммирования, в том числе автоматический анализ свойств про- грамм и их преобразования, осуществляемые с помощью других, ~ специальных программ. Поэтому нас интересуют алгоритмы, ко-: торые могли бы но любой предъявленной программе установить, ," завершит ли она работу нли будет «цнклить», дают ли две программы, исходная и оптимизированная, один и тот же результат, ' является ли проивзольная предъявленная Алгол-программа сии; таксически правильной и т.

д. Массовые алгоритмические проблемы формулнруются следующим образом. Необходимо указать алгоритм, который бы опре, делял, обладает лн предъявленный объект из некоторого класса '. обьентов интересующим иас свойством; друтнмн словами, при- 47 надлежит ли он множеству М всех объектов, обладающих этим свойством. Если существует такой частичный алгоритм„то говорят, что множество перечислимо, а поставленная массовая алгоритмическая проблема частично разрешима. Если этот алгоритм к тому же всюду определен, то множество М разрешимо и поставленная проблема также разрешима. В этом параграфе мы убедимся в существовании неразрешимых проблем и даже проблем, которые не являются частично разрешимыми, что свидетельствует о существования невычнслимых функций.

Теоремы этого параграфа будут использованы в последующих главах для доказательства неразрешимости некоторых проблем теории схем программ. Обсуждаемые понятия введем формально для множеств слов. Пусть à — алфавит, М ~ à — некоторое множество слов в атом алфавите. Характеристической 4ункцией множестеа ЛХ яааывается предикат Рм.

Г» — (О, 1), всюду определенный на У»: ~ 1, если ае=М„ гХастичная характеристическая 4ункцил множестваМ вЂ” зто функция Нм.. У»-~- (Ц, определенная только для слов из М и имеющая вид Нм (сс) = 1 для всех сс ~= М. Множество М называется рагресииммм, если его характеристическая функция вычнслима. Множество М перечислимо, если его частичная характеристическая функция вычислима. Разрешимость множества ЛХ означает, что существует всегда останавливающаяся машина Тьюринга Тг „позволяющая для любого слова в алфавите вечерев конечное число шагов установить, принадлежит ли это слово множеству М или нет.

Перечислнмость множества М означает, что существует машина Тьюринга Тн, которая останавливается в том и только в том случае, если предъявленное слово принадлежит множеству М. Машина Тн не позволяет точно установить, принадлежвт заданное слово множеству М или нет, так как отсутствие ответа к некоторому времени не несет никакой информации о том, появится он позже или нет. Однако если машина Тн остановилась, то мы знаем, что предъявленное слово принадлежит М.