1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 15
Текст из файла (страница 15)
Здесь воаможны дза исхода. Если в программе машнны Т есть команды, которые могут продолжить протокол, то управление передается на шестую, отвергающую группу команд. Если же таких команд нет, то автомат переходит в заключительное состояние и активизирует головку 1, которая обозревает символ ~. Автомат останавливается, допуская слово-протокол на ленте. Мы надеемся, что несмотря на неформальность доказательства и отсутствие деталей проведенные рассуждения убеждают в том, что построенный двухголовочный автомат допускает слово на своей ленте только в том случае, если оно является конечным протоколом работы машины Т над словом а. В любом другом случае слово на ленте отвергается (например, если оно является суффиксом бесконечного протокола неостанавлнвающейся машины Тьюринга, илн, наоборот, конечным протоколом, надстроенным «лишннмн» конфигурациями, или конечным протоколом другой машины Тьюринга, или протоколом работы машины Т над другим словом). Д 3 а д а и и е 3.4.
Постройте машину Тьюриига, которая преобразует деоичкме слова е «обретиые», т. е. »«мекает О ие $ и $ ие О. Постройте дзулголозочвый аетомлт, моделирующий работу атой машины иод словом $01. Т е о р е м а 3.9. Проблема пустоты двух«ело«очных автамато«не я«ляется частично разреши.иой. Д о к а э а т е л ь с т в о. Используем проблему зацикливания машин Тьюринга и метод сведения. Предположим, что проблема пустоты двухголовочных атоматов частично разрешима. Тогда оказывается частично разрешимой проблема азцикливания 64 машин Тъюринга.
Действительно, частичкый алгоритм распознавания зэтшкливапкя с~~дятел к следующим действиям. $. Для зэданкой машины Тьюринга Т и иачалыюго слова а строится двухголовочиый автомат А, моделирующий работу машины Т над словом а. 2. Если частичный алгоритм, выясняющий, пуст ли автомат А, обнаруживает, что Мл = О, то это значит, что машина Т зацикливается, работая иад словом а. Существование частичного алгоритма распознавания эадиклкваиия противоречит теореме $А, что н опровергает предположение о частичной разрешимости проблемы пустоты для двухголовочных автоматов.
( ) Т е о р е и а ЗЛО. Проблема эквивалентности двухсолоаочнмг амваматоа нс яаластсл частично разрешимой. Д о к а з а т е л ъ с т в о. Предположим противное. Тогда оказывается частично разрешимой проблема пустоты двухголовочных автоматов. Действительно, пусть А — произвольный фиксированный пустой дзухголовочный автомат (пример такого автомата легко построить). Частичный алгоритм распознавания пустоты проиавольного двухголовочного автомата очевиден: надо установить, эквивалентен ли этот автомат пустому автомату Ас. Получено противоречие только что доказанной теореме 3.9.
( ) Доказательство теоремы ЗЛО демонстрирует роль понятия пустоты при исследовании проблемы эквивалентности автоматов. Аналогичную роль это понятие играет и при изучении эквивалентности других объектов и формальных систем (схем программ, акеиоматик, грамматик формальных языков и т. п.).
Из неразрешимости проблемы пустоты немедленно следует неразрешвмоеть проблемы эквивалентности, так как пустоту можно рассматривать как частный случаи эквивалентности (например, эквивалентность фиксированному пустому автомату, пустой машине Тьюринга и т. д.). Если же проблема пустоты разрешима (частично разрешима), то проблема эквивалентности должна исследоватъся независимо, так как в общем случае из разрешнмоств (частичной разрешимостк) пустоты не следует разрешимость (частичная разрешимость) проблемы эквивалентности.
Например, проблема пустоты разрешима для многоленточных автоматов, но проблема нх эквивалентности открыта (для случая трех н более лент). Краткий обзор и кеммеитарни В етой главе приводится всего лишь несколько фактов из теории конечных автоматов н не включены сведения даже о тех автоматах, которые играют активную роль при изучении ие рассматриваемых в книге проблем теоретического программирования. В частности, не упоминалиеь магазинные н стековые автоматы, нрименяввшеся при решеиик ряда задач теории схем программ. З в.ккегез,в.к.сезель е а 6$ Мы спустили также изложение основ теории формальных яаыиов, тесно связанной как с теорией автоматов, так н со многими рааделами теоретического программирования. Однако для анакомства с основной проблематикой теории схем программ можно ограничиться приведенным минимумом сведений.
Читателям, желающим более подробно познакомиться с теорией автоматов и Формальных языков, будет полеана обзорная статья Ахоу и Ульмана 1801. Особое внимание в этой главе было уделено многолевточвым автоматам. Изложение в целом следует работе Берда ~8Я. Фактически наложение пп.
2 1 — 2.4 получено переносом доказанных в ~851 результатов для двухленточных схем Берда на я-ленточные схемы, а в и. 2.5 приводится результат из ~8Я о разрешимости эквивалентности двухленточных автоматов. Проблема эквивалентности я-ленточных автоматов для я > 3 является одной из наиболее вызывающих открытых проблем теоретического программирования, которая почти 80 лет не поддается усилиям математиков. Кинбер ~281 доказал разрешимость проблемы эквнвалентности в классе автоматов, совершающих ограниченное число переходов па все ленты, за исключением, быть может, двух. Другой разрешимый подкласс многоленточных автоматов, каждое состояние которых содержится не более чем в одно~ цикле, был выделен ,Льюисом 1И71.
ГЛАВА4 СТАНДАРТНЫЕ СХЕМЫ ПРОГРАММ Схема программы — центральное понятие современной теории программирования, основной инструмент исследования свойств и преобразований программ. После обсуждения методологических предпосылок возникновения этого понятая н неформального введения в основную проблематику схем программ определим класс так называемых стандартных схем. На базе стандартных схем будут введены основные понятия, связанные со схемами программ, главное иэ них — отношение функциональной эквивалентности схем. б 1. Схемы программ 1Л. Программы. Программа выступает как промежуточное звено при общении человека с вычислительной машиной, связывая поставленную задачу с процессом поиска ее решения на машине.
Понятие аадачн очень емко, и его трудно уточнить, не'обеднял, даже на интуитивном уровне, в силу большого разнообразия-целей, содержания н форм задач, которые сейчас решаются с помощью ЭВМ. Нам достаточно представлять задачу как функцию над множеством данных — объектов, кодирующнх заданную и искомую информацию. Будучи посредником между задачей и машиной, программа задает некоторую механическую процедуру решения задачи, являясь одним иэ способов задания алгоритма. Поэтому программа обладает всеми общими свойствами алгоритм мов: является конструктввным объектом; работает конечное время для тех наборов исходной информации, для которых вычисляемая функция определена; для программы характерны массовость (применимость ко множеству разных начальных данных) и однозначность.
Конструктивный характер программы проявляется в том, что она представляет собой конечный текст на некотором формализованном языке, который можно изучать и преобразовывать методамн формальной лингвистики. Синтаксическая сторона программы выходит на первый план в начальной стадии программирования: на этаке составления программы и в первых фазах трансляция. Соответственно в теоретическом программировании возникают такие задачи, как проблема распознавания синтаксической правильности программ, нахождение оценок сложности синЗз 67 таксического анализа, конструирование и исследование классов формальных языков, которые могут служить основой для разработки языков программирования с новыми синтаксическими свойствами и воэможностями, и т.
п. С другой стороны, программа определяет алгоритм решения задачи (алгоритм нахождения значений функции), генерируя последовательность действий машнны. Каждое иэ этих действий осуществляет некоторый швг преобразования данных и выаывается соответствующими синтаксическими конструкциями языка.
Каждая отдельная конструкция и нх совокупность несут определенную смысловую нагрузку. Смысл языковых конструкций н всей программы в целом — семантическая сторона программы. Основные проблемы как практического программирования, так н теории схем программ связаны с семантикой программ, с изучением и исполыюванием тех свойств и преобразований, которые сохраняют семантику и инвариантны к синтаксису программы.
Программа универсальна в том смысле, что любой алгоритм можно запрограммировать. Чтобы зто утверждение не было похоже на тезис, его можно переформулировать, используя формальное понятие вычнслимой функцни и фиксируя класс программ (т. е. язык программирования, семантика которого формализована). Ершов [13! построил в некотором смысле минимальный класс, содержащий программы нахождения значений любой вычислимой функции, заданной, например, машиной Тъюрингв. Этот класс включает программы, записанные на языке программирования, который можно назвать микро-Алголом. Язык включает только простые переменные, операторы присваивания, условные операторы и операторы перехода на метки. При этом правые части операторов присваивания могут содержать только арифметические выражения вида л+ 1, а логические выражения в условных операторах имеют вид отношения х = у, где х н у — простые переменные.
Воспользовавшись такой связью между программами и вычислимыми функциями, можно перенести на программы те свойства машин Тьюринга и те резулыаты, о которых шла речь в гл. 1. В частности, в терминах программ можно переформулировать проблемы остановки, зацикливания, пустоты и другие. От больпшнства автоматических преобразований программ (оптимизация, трансляция и др.) требуется, чтобы они гарантировали функциональную энвивалентность: исходная и преобразованная программы должны вычислять одну и ту же функцию. Так же, как и в случае машин Тьюринга, универсальность программ делает нх мощным средством решения разнообразных задач, но имеет свои теневые стороны в том случае, когда сами программы становятся объектом исследования.
Следствием универсалъности является невозможность иостроения полезной теории программ, базирующейся на учете лишь их функциональной природы, так как в этой теории нетривиальные проблемы оказываются чтривиально иеразрешимымиэ. ВВ Кроме того, программы являются объектами более сложной структуры, чем традиционные системы описания алгоритмов.
Современные универсальные языки программирования предоставляют в распоряжение программиста богатый набор программных примитивов. Приведем список наиболее распространенных. А. Средства описания структур данных. 1. Константы. 2. Простые переменные. 3. Массивы. 4. Сложные структуры данных — списки, магазины, очереди и т.п. 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
