1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 5
Текст из файла (страница 5)
Связь между разрешимыми и перечислимыми множествами (и, следовательно, между разрешимыми я частично разрешимымн проблемами) устанавливает следующая Т е о р е м а 1.1 (Пост). Многкестго М с: е'» рагреияьво тогда и только тогда, когда ЛХ и его дололнение М = У» ~ М перечисли мы. До ка з а тел ь ство. Иэ разрешимости М следует его перечислимость. Действительно, машину Тьюринга Тг, зычно. ляющую характеристическую функцию множества М, легко преобразовать в машину Тн, добавив к программе маншны Тг 18 :::исмаилы, зацикливающие ее в том случае, когда опа останавливается с результатом О.
Новая машина задает частичную харак' теристическую функцию множества М. Пусть Тн, к Тн- — машины Тьюринга, задающие частичные ы характеристические функции множеств М и соответственно М. ' Алгоритм распознавания, устанавливающий, принадлежит ли слово а множеству М, сводится к следующей процедуре. Выколкяется по одной команде каждой машины Тьюринга (с одним и тем же начальным словом сс па лентах). Если после выполнения одной команды машина Тя остановится, то результат работы алгоритма — символ $.
Если остановится Тя, то результат — символ О. Если ии одна из машин яе остановится, то выполняется следующая пара команд, и т. д. Так как а — элемент или иэ М, или из М, то через конечное число шагов либо Тнм, либо Тя остапом вится. Таким образом, алгоритм вычисляет значения характерис, тической функции множества М, и можно построить машину Тьюринга Тгм, реализующую этот алгоритм, к, следовательно, :, множество М разрешимо. ( ) Определение разрешимых и перечислимых мяожеств можно ( перенести ка числовые множества и множества,' элементами ко(торых являются объекты более сложной структуры. Примеры : разрешимых множеств: пустое множество; множество всех слов ; в некотором алфавите; множество всех словарных представлений ! машин Тьюринга кад алфавитом т'.
Теперь поэиакоыимся с не' разрешимыми множествами (неразрешимыми проблемамп) и с не'; перечислимыми множествами (проблемами, ие являвицимися час! тично разрешимыми). Задание 1.3. А. Покажите, что множество (а" Ь" ( я ~ Ц слов з алфзззте (а, Ь) разрешимо. Б. Пусть множеспа слов Мт и Мз рззре1пимы, Мз и Мз — перечжлимы. Покажите спрззедлнзость следузкцик утзержденнй: ре ~ Мы Мд Ц Мз, ' Мг Д Мз — разрешимые, з Мз 0 Мы Мз Д Мы Мт () Мз Мг Д Мз— , перечислимые множества. Б. Покзжвте, что облзоп определения любой зычисламсй функции— перечнслвмое миожестзо. Г.
Покажите, что иепустое мнсжеогзо перечислимо тогда и только то: гда, когда оно является областью значений некоторой частичной кычислнмон . функции. 2.2. Проблема остаиовии. Машина Тьюринга, начав работу кад некоторым начальным словом па ленте, или останавливается, или работает бесконечно. Было бы полезно иметь алгоритм, ко; который для любой машины Тьюриига Т иад алфавитом У и для ,:. любого слова сс в этом алфавите выяскял, остановится ли машина, ~ начав работу иад словом а. Проблему остановки можно сформулировать также в терми!:,нах множеств. Пусть М,— множество всех пар слов в алфави:„- те У, в каждой паре первое слово — словарное представление ие- чз которой машины Тьюринга, второе — такое слово, что эта машина останавливается, начав работу над ним.
Является лв множество М, нераэрешимым1 Т е о р е м а $.2 (Тьюринг). Проблема освииимки маиии Тьюринга неразрешима. Д о к а э а т е л ь е т в о. Необходимо установить, является ли вычислимов характеристическая функция Рм,. Уа«-~ (О, 1). Предположим, что зто так и Тг — машина Тьюринга, вычисляющая эту функцию. Иэ вычислимости функции Ры, и разрешимости множества М, словарных представлений машин Тьюринга в алфавите Г следует вычвслимость частичной одноместной функцин 6: Га-~- (О, Ц, которая задается следующим образом: 6(а) =- = Рм, (сс.
с«) для всех и ~ М, и 6 не определена для всех а ~ М,. Функция 6 концентрирует внимание на машинах Тьюринга. применяемых к собственным словарным представлениям. Введем еще одну частичную одноместную функцию К: г'а-~ -~ (О). Эта функция определена только для тех слов, для которых 6 (и) = О, причем для всех этих слов К(и) =. 6(а) =- О. Функция К вычислима, если вычислима функция 6. Действительно, машина Тьюринга Тк совпадает с машиной Та за исключением случая, когда То останавливается: машина Тк продолжает работу, выясняет, каков результат — $ или О„и в первом случае зацянливаетсн, во втором — останавливается.
Пусть (3к — словарное представление маппгны Тк в алфавите У. Попробуем выяснить, определено ли значение К ((3к), т. е. понробуем решить проблему остановки для пары — машины Тх в ее словарного представления. Допусткм, что значение К (рк) не определено, т. е. машина Тк не останавливается, начав работу над словом рк. Т~~да Р~, (рк.
рк) =- О, 6(3эх) = 0 в К(~~) = О. т, е. значение К((3к) определено, что противоречит яредположению. Предположим тенерь, что значение К (рк) определено, т. е машина Тк останавливается, начав работу над словом (3к. Тогда Рм, (рк, 33к) =- $, 6 ((3к) =- $ и К (рк) не определено, что также противоречит предположению. Оба допущения о функции К приводят к противоречию, что опровергает гипотезу о вычиелимости функции Гм и разрешимости множества М,.
Ц Теорема $.2 устанавливает неразрешимость проблемы остановки для машин Тьюринга и демонстрирует существование невычислимых функций (характеристическая функция Ры ). Иэ тезиса Тьюринга следует, что для неразрешимых проблем нельзя построить алгоритм, который решал бы их «механически», например, с помощью ЭВМ. Это означает, что нераэрешвмая проблема представляет собой слишком общую задачу, включающую неноторые «вырожденные» случаи (клк, например, работу машины Тк над собственным словарным представлением).
Попытки упростить неразрешимые проблемы путем исключения особых случаев 20 тут значительно обеднить их, сделать тризиазьнымн с точки реиня практики. В частности, теорема 1.2 не исключает воаможости, что проблема остановки может оказаться разрешимой для которого узкого класса машин Тьюринга. Задание 1.4. А. Покажите, что проблема остаиозки кашки Тьюрзпга является час. чио разрешякой. Б. Покюките, что проблеял остановка разрешима для класса мал|за ~Гьшрияга, прогрокка которых содорпшт лишь одну команду.
2.3. Проблема пустой ленты и метод сведения. Попробуем '„установить„разрешима ли более частная проблема остановки, именно остановка машин Тьюринга, применяемых к пустой лен'те, т. е. к лепте, содержащей только символ ~. Другими словами, надо выяснить, является ли разрешимым множество М, словар- х представлений всех тех мапшн Тьюринга, которые останав,ливаются, начав работу над пустой лентой.
Т е о р е м а !.3. 11роблема пустой леншм неразрешима. Д о к а э а т е л ь с т в о. Каждой паре (Т, я), где Т вЂ” неторая машина Тьюринга, а я — слово в ее алфавите, соаоста' им машину Т, программа которой совпадает с программой ма- нны Т, за исключением того, что, начав работу, машина Т "тирает начальное слово на ленте н вместо него записывает слово Конструкция машины Т, очевидна: к программе машины Т обавляются подходящим образом команды машины из аадаия 1.2А. Машина Т„, начавшая работу с пустой лептой, ведет себя осле записи слова а так же, как н машина Т, примененная к ш.
частности, машина Т остановится в том и только в том случае, ' ля остановятся машина Т. Предположим, что проблема остановки вшпп Тьюринга с пустой лентой разрешима. Тогда окажетси ';разршнимой проблема остановки в общем случае. Действительно, цтобы узнать, останавливается ли некоторая мапшна Т, примененэгая к слову а, следует сконструировать машану Т„. Выяснив, апавлизается ли Т при пустой ленте, мы тем самым узнаем, таназлнвается ли Т. Это нротиворечит теореме 1.2, что и опровергает предположение о разрешимости проблемы пустой ленты.
Д.; В только что проведенном дояазательстве использована сле'йдующзя схема рассуждений: выполнив некоторые вспомогательбпые построения, мы предполагаем разрешимость исследуемой 'проблемы, что в силу проведенных построений дает нам возможээость решать другую проблему, о которой, однако, известно, что она неразрешима. Полученное противоречие докааывает неразрешимость исследуемой проблемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
