Игошин Математическая логика и теория алгоритмов (1019110), страница 91

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 91)

На шаге с номером С(т, и) этот алгоритм вычисляет т-й элемент множества М„, и если элемент совпадает с и, то он относит его в множестве У. Таким образом, и е Усь и е М„. Итак, У порождается алгоритмом й, т.е. У перечислимо. Поскольку дополнение (у множества Усостоит из всех таких и, что и я М, то й' отличается от любого перечислимого множества хотя бы одним элементом. Поэтому й' не является перечислимым. Следовательно, на основании теоремы 35.6 множество Унеразрешимо, что и завершает доказательство. П Доказанная теорема фактически включает в себя в неявном виде теорему Геделя о неполноте формальной арифметики, о которой мы подробно будем говорить в заключительном параграфе этой главы.

365 Подведем некоторые и т о г и. Итак, эффективно заданное множество — это множество, обладающее разрешающей или перечисляющей функцией (алгоритмом). Объединение и пересечение перечислимых множеств перечислимы. Непустое множество М~ Ф разрешимо тогда и только тогда, когда оно само и его дополнение перечислимы. В частности, отсюда следует, что всякое непустое разрешимое множество перечислимо. Тем не менее сушествует перечислимое, но неразрешимое множество натуральных чисел.

В теореме 35.7 такое множество описано. Другим примером такого множества является множество М= (х: А„(х) определен), т.е. множество номеров самоприменимых алгоритмов. Таким образом, перечислимость — более слабый вид эффективности, нежели разрешимость. Хотя перечисляющая процедура и задает эффективно список элементов множества М, поиск данного элемента а в этом списке может оказаться неэффективным: это неопределенно долгий процесс, который в конечном счете остановится, если а е М, но не остановится, если а и М.

В случае же перечислимости и дополнения М перечисляющая процедура для М становится эффективной и гарантирует разрешимость множества М. $ 36. Неразрешимые алгоритмические проблемы Алгоритмическая проблема — это проблема, в которой требуется найти единый метод (алгоритм) для решения бесконечной серии однотипных единичных задач. Такие проблемы называют также массовыми проблемами. Они возникали и решались в различных областях математики на протяжении всей ее истории.

Примеры таких проблем рассматривались в З 3!. Математики в начале ХХ в. столкнулись с тем, что для некоторых массовых проблем не удается подобрать общий алгоритм для их решения. В связи с этим возникла необходимость дать точное определение самому понятию алгоритма. Мы познакомились с несколькими способами такого уточнения, и в настоящем параграфе приведем примеры алгоритмически неразрешимых массовых проблем. Сначала в качестве понятия, уточняющего понятие алгоритма, будем использовать понятие машины Тьюринга. Затем рассмотрим проблему алгоритмической разрешимости в рамках общей теории алгоритмов.

Нумерация алгоритмов. Понятие нумерации алгоритмов — важное средство для их исследования, в частности для доказательств несуществования единого алгоритма для решения той или иной массовой проблемы. Посмотрим сначала на это понятие в рамках нашей общей теории алгоритмов. Поскольку любой алгоритм можцо задать конечным описанием (словом) (например, в конечном алфавите знаков, используемых при наборе математических книг), а множество всех конеч- Збб ных слов в фиксированном конечном алфавите счетно, то множество всех алгоритмов счетно. Это означает наличие взаимно-однозначного соответствия между множеством Ж натуральных чисел и множеством всех алгоритмов, рассматриваемым как подмножество множества А1* всех слов в алфавите А1, выбранном для описания алгоритмов (у: Ф вЂ” > А1').

Такая функция называется нумераиией алгоритмов. Если д(л) = А, то число и называется номером алгоритма А. Из взаимной однозначности отображения у следует существование обратной функции у ', восстанавливающей по описанию алгоритма А„его номер в этой нумерации у-'(А„) = л. Очевидно, что различных нумераций много. Нумерация всех алгоритмов является одновременно и нумерацией всех вычислимых функций в следующем смысле: номер фун- кции Г" — это номер некоторого алгоритма, вычисляющего~ Ясно, что в любой нумерации всякая функция будет иметь бесконечное множество различных номеров.

Существование нумераций позволяет работать с алгоритмами как с числами. Это особенно удобно при исследовании алгоритмов над алгоритмами. Отсутствие именно таких алгоритмов часто приводит к алгоритмически неразрешимым проблемам. Нумерация машин Тьюринга. Опишем теперь более конкретный процесс нумерации всех машин Тьюринга, который используем при построении примера невычислимой по Тьюрингу функции. Будем считать, что для обозначения внутренних состояний машин Тьюринга используются буквы бесконечной последовательности: д,, дь д,, ..., д„, ..., а для обозначения букв внешних алфавитов используются буквы последовательности: ам а„ап ..., а„...

Выразим (или, как говорят, закодируем) все символы этих бесконечных последовательностей словами конечного стандартного алфавита (аг» 1, д, С, П, Л) по следующим правилам: д;(1 = О, 1, ...) обозначим (закодируем) словом из 1+ 1 букв д: дд... д; а, (у = 1, 2, ...) обозначим (закодируем) словом из / единиц: 11...1. В стандартном алфавите программу машины Тьюринга можно записать в виде слова, руководствуясь следующим правилом.

Сначала все команды программы переводятся на язык стандартного алфавита, для чего в записях этих команд д;а, -» д,а„Х где Х е (С, П, Л), опускается символ « — >», а буквы дь а, дь а„заменяются соответствующими словами стандартного алфавита. Затем полученные слова-команды записываются подряд в любом порядке в виде единого слова. Например, программа машины Тьюринга, рассмотренной в примере 32.1, в этих обозначениях имеет вид: д,ав — » дга«П, д,а, — > -> д,а, П, дзав -» два, С, д,а, — > дта, П. Опускаем символ «-»», заменяем буквы словами стандартного алфавита и в результате полу- 367 чаем следующие слова в стандартном алфавите, кодирующие соответствующие команды: дда,ддда,П, дд1дд1П, ддда,д1С, ддд!ддд1П.

Выписываем эти слова подряд и получаем слово, кодируюшее программу данной машины Тьюринга: ддаьдддаьПдд) дд1 П дддаьд1 Сддд) ддд1'П, Нетрудно указать алгоритм, позволяющий узнавать, является ли слово в стандартном алфавите программой некоторой машины Тьюринга. Такой алгоритм может, например, состоять в следующем.

Нужно анализировать все подслова данного слова, заключенные между всевозможными парами букв из (С, П, Л). Эти подслова должны иметь следующую структуру: сначала записаны несколько букв д, затем аь или несколько букв 1, затем снова несколько букв д и, наконец, снова аь или несколько единиц. Таким образом, каждая машина Тьюринга вполне определяется некоторым конечным словом в конечном стандартном алфавите. Поскольку множество всех конечных слов в конечном алфавите счетно, то и всех мыслимых машин Тьюринга (отличающихся друг от друга по существу своей работы) имеется не более чем счетное множество. Перенумеруем теперь все машины Тьюринга, для чего все слова стандартного алфавита, представляющие собой программы всевозможных машин Тьюринга, расположим в виде фиксированной счетно-бесконечной последовательности, которую составим по такому правилу: сначала выписываются в какой-нибудь фиксированной последовательности все однобуквенные слова: аь, ан ..., аь, представляющие программы машин Тьюринга (множество таких слов конечно, потому что конечен стандартный алфавит, из букв которого строятся слова), затем выписываются все двухбуквенные слова аь,н ..., а„, представляющие программы машин Тьюринга (множество такйх слов также конечно, потому что конечен стандартный алфавит), затем выписываются трехбуквенные слова и т.д.

Получится последовательность программ аь, ан ап ..., а„, ... всех мыслимых машин Тьюринга. Число и будем называть номером машины Тьюринга, если программа этой машины записывается словом аы Существование иевычислимых по Тьюриигу функций. Теорема 36.1. Существует функция, не вычислимая но Тьюрингу, т. е, не вычислимая ни на одной машине Тьюринга. Д о к а з а т е л ь с т в о. Функции, о которых идет речь, представляют собой функции, заданные и принимающие значения в множестве слов в алфавите А, = (Ц. Ясно, что множество слов в алфавите А, = (1) счетно. Следовательно, рассматривается множество всех функций, заданных на счетном множестве и принимающих значения в счетном же множестве. Как известно, это множество имеет мощность континуума.

С другой стороны, поскольку множество всевозможных машин Тьюринга, как мы установили в пре- Зб8 змдущем пУнкте, пеРенУмеРовав их, счетно, это и множество фУнкций, вычислимых по Тьюрингу, также счетно. Континуальная „ошность строго больше счетной. Следовательно, существуют функции, не вычислимые по Тьюрингу. Е1 Доказанная теорема есть чистая теорема существования. Интересно получить пример конкретной функции, не вычислимой по Тьюрингу. Пример Зб.2.

Укажем конкретную функцию, которую нельзя вычислить ни на какой машине Тьюринга. На основании тезиса Тьюринга это будет означать, что не существует вообще никакого алгоритма для вычисления значений такой функции. Рассмотрим следующую функцию ~у(а) на словах в алфавите А, = (Ц. Для произвольного слова а длиной и в алфавите А, = (Ц положим: ~у(а) = 1)„1, если слово а перерабатывается машиной Тьюринга с номером л (см. предыдущий пункт) в слово )З„алфавита А, = (Ц; чг(а) = 1 в противном случае. Докажем, что функция фа) не вычислима по Тьюрингу. Допустим противное.

Это означает, что существует машина Тьюринга Тсо стандартным алфавитом (аа, 1, д, П, Л», вычисляющая эту функцию. Пусть /с — номер этой машины в нумерации, описанной в предьиущем пункте. Посмотрим, чему равно слово ~у(1~) (напомним, что 1ь = 11... 1 — слово из lс единиц), являющееся значением функции у(а) при а= 1".

Предположим, что машина Т перерабатывает слово 1ь в слово Ц в том же алфавите А, = ( Ц. Тогда по определению вычислимости функции чг(а) на машине Тато означает, что у(1") = (1». Но с другой стороны, по самому определению функции чг(а) это означает, что ~с(1~) = Ц1. Полученное противоречие доказывает, что машины Тьюринга, вычисляющей функцию у(а), не существует.

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

Характеристики

Список файлов книги