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

Такой метод доказательства '' взывают меш4яуом сзядевия: известная неразрешимая проблема водится к исследуемой, поэтому последняя также неразрешима. етод сведения используется и в случае, когда докааывается, что рассматриваемая проблема ие является частично разрешимой. етод сведения широко применяется и в теории схем программ 2$ Как правило, осуществляется последовательный многоступенчатый процесс сведения одних проблем к другим, и часто «базовой» неразрешимой проблемой в этой цепочке оказывается проблема остановки машин Тьюринга. (Однако метод сведения не универсален, так как существуют взаимно несводимые неразрешимые проблемы [61).) Другая «базовая» неразрешимая проблема, часто используемая в доказательствах методом сведения,— проблема яюждества слов Поста [132[.

Она формулируется следующим образом. Пусть Х = (аю а,..., и„) и Г = ([)г, [)з,..., р ) — два равной длины набора слов в алфавите [г. Пару (Х, г') называют системой Поста. Непустую конечную последовательность индексов („г„..., ую где все индексы ~$ н ~(п, называют решением сисягемы Поста, если ииаь... сгг„= ~;,()и...

р, (слева и справа слова, полученные конкатенацией выбранных слов соответственно нз Х и У). Существует лк алгоритм, который обнаруживает, имеет ли система Поста решеннег Пост показал неразрешимость этой проблемы для алфавитов, содержащих более одного символа. В то же время проблема Поста частично разрешима. Задание 1.5. А. Проб. вема юпошольяоожи для машан Тьюринга состоит з следующем: .существует ли алгоритм, который для любой машины Тьюрюпп Т узнаяг, будет ли машина останавливаться при любом начальном слоне нз яоито (другими словами, яялястся ли функция г"т всюду определенной)г Покажите (мстсдом сяодбияя) неразрешимость атой проблемы.

Б. Машины Тьюринга Т н Т' оявшмлеятмм, если гг — — гт,. Проблема зкянззлоптности машин Тьюринга состоит я обнаружении алгоритма, который для любой пары машин Тьюрюп'а смог бы уст»но»ать, зкяиязлснтны они илн изт. Покажите (мотодом сзодення), что проблема зкзнэзлонтности неразрешима. 2.4. Проблема зацикливания.

Установив существование нераареюимых проблем и множеств, продемонстрируем сугцествование иеперечислимых множеств и проблем, которые не являются частично разрешимыми. Проблема зацикливания состоит в следующем: существует ли алгоритм, хотя бы частичный, который выясняет заранее для произвольной машины Тьюринга и произволыюго начального слова г», будет ли машина работать бесконечно долго, т, е. надо установить, будет ли разрешимым или перечислимым множество М, С Уо* всех пар слов таках, что первое слово — словарное представление некоторой машины Тьюринга, а второе — слово, на котором зта машина зацикливается.

Т е о р е м а ».4. Проблелга заг(ииливанил машин Тьюринга не лвллелгсл частично разрешимой. Д о к а з а т е л ь с т в о. Из теоремы 1Л н перечислимости множества М, (см. п. 2.2) следует, что дополнение М, множества М, до множества всех пар слов в алфавите У неперечислимо, так как в противном случае оказалось бы разрешимым множество М,. Но М, = М, [) Ме, где Мв — множество всех пар слов, первые слова в которых являются словарными представлениями машин '1'ьюринга, а Мд — его дополнение.

Так как множество М~ всех словарных представлений машин Тьюринга разрешимо, множество Мд и множество Мл разрешимы (см. задание 1.3В). Предположим, что проблема зацикливания частично разрешима, а множество М, — пвречислимо. Тогда окажется перечислимым множество М„что неверно.

~ ~ Обратите внимание, что разрешимые множества могут включать (как собственныв подмножества) пвречислимыв множества, которые, в свою очередь, могут содержать неперечислимыв подмножества. Зто означает, что разрешимые множества отличаются, не меньшей количественной мощностью, а еменьшим разнообразиемэ своих элементов. 3 а д а н и е $.6.

Покажите, что не являются частично разрешимыми. сл едующие проблемы: А. Проблема зацикливания машин Тьюринга с пустой лентой. Б. Проблема тотальности машин Тьюринга. .В. Л'роблема аустоты машин Тьюринга (машина пуста, если она зацикливается при любом начальном слове). Г. Проблема эквивалентности машин Тьюринга. Д. Проблема пустоты систем Поста (система Поста пуста, если она не имеет ни одного решения).

Краткий обзор и комментарии Понятие вычислимости основывается на двух тесно взаимсвязанных понятиях — понятии вычислимой функции и пон алгоритма. Вычислимая функция — это функция, для которой существует алгоритм нахождения значений вычислимой функции. Оба понятия в интуитивной форме существуют века, но до 30-х гг. этого столетия они играли роль методологических концепций, а не точных математических объектов. Формализация вычисли- мости была осуществлена двумя способами. Черч и Клини определили вычислимые функции, отождествив их с рекурсивными. Черч ~9Ц высказал гипотезу о тождественности класса рекурсивных функций и класса всюду определенных вычислимых функций, и эта гипотеза известна как тезис Черча. Клини 1И31 определив понятие частичной вычислимой функции и обобщил тезис Черча, постулировав тождественность этого класса функций классу частично рекурсивных функций.

С другой стороны, Пост Ы313 и Тьюринг ~14И уточнили понятие алгоритма и через алгоритм определили класс вычислимых функций. Согласно данному уточнению, алгоритм — это процесс, совершаемый некоторой гипаер тической машиной, конструируемой в рамках точных матемащ ческих понятий. Машины Поста и Тьюринга отличаются в арф щественных деталях, но общее у них то, что они с помоарФВ ограниченного набора средств могут имитировать все извмжЯ~ интуитивные алгоритмические процессы. Класс функций, зиачФ1 которых можно находить с помощью машин Тьюринга — П~ был объквлеи классом выаислимых фуиииий (тезис Тыор$щф~, и было показано, что такое определение вычкслимых фунвций эквивалентно определению Черча — Клики.

Позднее предла«ались другие способы формализации понятий алгоритма и вычислкмой функции — более сложные «машнны» или, наоборот, системы с минимумом средств, как, например, нормальные алгоритмы Маркова (401. Они могут быть более удобными для каких-нибудь специальных целей или классов алгоритмов, но онн эквивалентны «классическим» формализациям.

Уточнение понятий вычнслимой функции и алгоритма позволило формализовать понятие существования решения массовых математических проблем, а именно, появилась воэможность переформулировать эту задачу как задачу о существовании (частично) вычнслимых функций, коднрующих заданную проблему.

(Следует отметить, что идеи Гяльберта и работы Геделя, связанные с исследованием «универсальных разрешающих процедур», обратили внимание ва класс рекурсивных функций н привели к появлению теаиса Черча.) Формализация понятия разрешимости дала воэможность установить существование целого ряда неразрешимых проблем в различных областях математики. С неразрешвмымв проблемамн в теорик схем программ мы неоднократно встретимся в атой книге. Факт существования таких проблем можно трактовать двояко. Можно считать, что проблема неразрешима, потому что она чересчур обща, включает «ненормальные» ситуации, и ее нужно переформулировать так, чтобы она содержала только те жизненные случаи, с которымн имеет дело (н успешно справляется) программист. Но, как уже указывалось, редко удается классифицировать реальные факты в явления так, чтобы онн были интересными и полезными, оставаясь одновременно в рамках раарешиммх проблем.

С другой стороны, можно попытаться обобщить теорию вычнслнмостн и разрешимости так, чтобы нераэревшмые проблемы «решались» в некотором новом интуитивном смысле. Но такое обобщение выведет нас за рамии современной математики. Литература по теории вычислимости и раарешнмостн обширна, Мы приводим лишь классические работы н несколько известных монографий Р9, 44, 6$, 7$, 74, 951, которые содержат довольно полную библиографшо по этой тематике.

ГЛЛВЛ 2 ГРАФЫ И МЕТОД РАЗМЕТКИ Понятие гра4а широко используется в программировании кав средство абстракции прн описании таких объектов, как программа, структура данных, а также при описании алгоритмов распознаваняя различных свойств программ н при преобразованиях программ.

В теории схем программ ве центральное понятие — схема программы — представляется в виде размеченного графа. Понятие разметки вводится как отображение, сопоставляющве вершинам илн дугам графа пометки иэ некоторого 4нксированиого множества пометок. В этой главе вводится терминология, связанная с понятием графа, а также описан метод разметки для решения задачи глобального анализа свойств. $1.

Пвнятие графа 1.1. Определение графа. Ориентированным мулыввграЯом (в далънейшем просто графаз, поскольку других графов мы не рассматриваем). называется тройка Г = ($1 Е, Ф), где г' — множество вершин, Š— множество дуг„а Ф вЂ” функция иэ Ев (ГО (в))г, е бс У. Дуга е иааызается входом (графа Г), если Ф (е) = (е, и) для и~ У Ц (в); выходом (гра4з Г), если Ф (е) = (и, ы) для и бс У Ц (ы); внутренней, если Ф (е) = = (им иг) для им иг ~ Р. Дуга е, явлюощаяся одновременно и входом, и выходом графа Г, называется висячей; для нее Ф (е)= = (м, е). Дуги, не являющиеся внутренними, будут называтъся также свободными. Мы говорим, что дуга е оедеж к вершние и, а верппша и являвтсн воняем дуги е, и записываем этот факт вак и = кон (е), если Ф (е) = (й, и) для и ~ У, й ~ г' Ц (в).

Мы говорим, что дуга е находит иэ вершины и, а вершина и является началом дуги е, р записываем это как и = нач (е), если Ф (е) = (и, й) для и е! К, и' ~Б У О (ы). Заметим, что в наших графах одну и ту же пару вершин и, й может соединять (т. е. выходить из и и вести к и') олъко угодно различных дуг. варят, что дуга е ингргденжна вершине и, если е выходит нлн ведет к и. Две дуги смежны, если существует хотя бы одна двитиая им обеим вершина. Множество дуг, смежных дуге е, 25 будет называться окрестностью дуги е и обозначаться окр (е). Вершние в называется наследником вершины о', если в графе имеется хотя бы одна такая дуга е, что Ф (е)=(о', о). Изображенный на рис.