Книга
← К списку книгЗагрузка разделов…
активнаАктивные записи участвуют в каталоге и синках. Неактивная книга скрыта, но не удалена из базы.
Книга
Основные понятия теории алгоритмов
Первые примеры алгоритмов встречаются уже в средней школе: алгоритм сложения натуральных чисел столбиком, алгоритм умножения двух натуральных чисел, алгоритм деления с остатком, процесс нахождения наибольшего общего делителя двух целых чисел, известный под названием алгоритма Евклида. Из других алгоритмов можно указать алгоритм разложения натурального числа на простые множители, извлечения квадратного корня из натурального числа, решения системы линейных уравнений методом Гаусса и т. д. Каждый из этих алгоритмов представляет собой некоторую вычислительную процедуру, выполнение которой не требует изобретательности или сообразительности, а состоит лишь в строгом следовании инструкциям.
Общие черты алгоритмов:
Дискретность. Алгоритм — это процесс последовательного построения объектов, идущий в дискретном времени таким образом, что в начальный момент задается исходный набор объектов, а в каждый следующий момент из набора объектов, имевшихся в предыдущий момент, по определенному закону (программе) получается новый набор объектов. Выполнение всякого алгоритма состоит из отдельных шагов. Каждый шаг обязательно завершается. Если выполнение алгоритма никогда не закончится, это означает, что алгоритм совершает бесконечное число шагов.
Детерминированность. Набор объектов, получаемых в какой-то момент, однозначно определяется набором объектов, полученных в предшествующие моменты.
Элементарность шагов. Закон получения последующего набора объектов из предшествующего должен быть простым и локальным.
Направленность. Должно быть указано, что надо считать результатом алгоритма.
Массовость. Начальный набор объектов может выбираться из потенциально бесконечного множества — множества возможных исходных данных этого алгоритма. При этом исхлдными данными для алгоритма могут быть лишь так называемые конструктивные объекты. Интуититвно, конструктивный объект — это такой объект, который построен (сконструирован) из некоторых исходных элементарных неделимых элементов фиксированного точно очерченного конечного множества по фиксированным правилам, так что строение этого объекта может быть полностью описано некоторым текстом на подходящем языке. Если фиксированы набор исходных элементов и правила конструирования объектов из них, говорят, что задан ансамбль клнструктивных объектов.
Типичным примером ансамбля конструктивных объектов является множество слов в данном конечном алфавите. При этом исходными элементами являются буквы алфавита, а способ конструирования состоит в построении конечных цепочек букв, т. е. слов. В частности, множество натуральных чисел N = {0, 1,2,...} может рассматриваться как ансамбль конструктивных объектов, ибо натуральные числа можно изображать, например, словами в однобуквенном алфавите {|}: 0 — пустое слово; 1 — слово |; 2 — слово || и т. д. Множества целых и рациональных чисел также могут рассматриваться как ансамбли конструтивных объектов.
Всякий ансамбль конструктивных объектов счетен. Более того, его всегда можно эффективно занумеровать, т. е. установить такое взаимно однозначное соответствие между ансамблем конструктивных объектов и множеством натуральных чисел, что по любому объекту можно вычислить его номер, а по любому натуральному числу п можно эффективно построить объект с номером п. Свойство эффективной нумеруемости мы примем за основной признак ансамбля конструктивных объектов. Итак, множество возможных исходных данных любого алгоритма — это некоторый ансамбль конструктивных объектов.
Понятие алгоритма, определяемое требованиями 1-5, не строгое. Это нестрогое понятие алгоритма обычно называется интуитивным понятием алгоритма.
При применении данного алгоритма к исходному данному возиожны следующие три варианта. 1) Применение алгоритма к исходному данному завершится через конечное число шагов, и алгоритм выдаст результат. В этом случае говорят, что алгоритм применйм к исходному данному. 2) Применение алгоритма к исходному данному завершится через конечное число шагов, но алгоритм не выдаст никакого результата.
Применение алгоритма к исходному данному никогда не закончится, т. е. алгоритм совершает бесконечное число шагов. В случаях 2) и 3) говорят, что алгоритм не применим к исходному данному. Множество возможных исходных данных, к которым алгоритм применим, называется областью применимости этого алгоритма.
Пусть X — множество возможных исходных данных алгоритма 21, а его результаты принадлежат ансамблю конструктивных объектов У. Пусть D С X — область применимости алгоритма 21. Будем говорить, что алгоритм 21 вычисляет функцию f : D —> У, которая каждому х Е D сопоставляет результат применения алгоритма 21 к х. Частичной функцией из X в Y будем называть любую функцию f : D —> У, где D С X. Таким образом, каждый алгоритм с множеством возможных исходных данных X, результаты которого принадлежат ансамблю конструктивных объектов У, вычисляет некоторую частичную функцию из X в Y.
В дальнейшем мы будем иметь дело с выражениями (частичными именными формами), в которых встречаются обозначения для частичных функций, и которые, следовательно, определены не при всех значениях свободных переменных. В связи с эти мы будем употреблять символ условного равенства ~ и будем считать, что предложение s ~ t истинно при тех значениях свободных переменных, при которых оба выражения s и t определены и имеют одинаковые значения или же оба не определены.
Интуитивное понятие алгоритма удовлетворяло математиков до тех пор, пока возникающие в математике проблемы, требующие нахождения алгоритма для решения некоторой совокупности родственных задач (или алгоритмические проблемы), удавалось решить путем указания конкретных алгоритмов. Положение изменилось в XX в., когда на первый план выдвинулись алгоритмические проблемы, положительное решение которых было сомнительным. Среди них — так называемая 10-я проблема Гильберта о разрешимости алгебраических уравнений в целых числах. Чтобы доказать несуществование алгоритма, надо иметь точное определение понятия алгоритма. Математические уточнения понятия алгоритма были получены в середине тридцатых годов в работах Гильберта, Гёделя, Чёрча, Клини и Поста.
Машина Тьюринга
Пост (1936) и Тьюринг (1937) независимо друг от друга предложили уточнение понятия алгоритма как процесса, который может совершаться подходяще устроенной ’’машиной”. Машины, введенные Постом и Тьюрингом, отличались не очень существенно и в дальнейшем стали называться машинами Тьюринга. Мы рассмотрим вариант машин Тьюринга, близкий к тому, который был предложен Постом.
Машина Тьюринга содержит следующие части:
Конечная лента, разбитая на конечное число клеток (или ячеек). В процессе работы машины к ленте могут пристраиваться новые ячейки, так что лента может считаться потенциально бесконечной. В каждой ячейке ленты записан (или содержится) один из конечного числа символов, составляющих внешний алфавит А = {«о, «1, . . ., ат}. Клетки, в которых записан символ «о, обычно обозначаемый 0, называются пустыми. Все вновь пристраиваемые ячейки являются пустыми.
Внутренняя память — некоторе устройство, которое в каждый момент находится в одном из конечного числа ’’состояний”, составляющих внутренний алфавит Q = {до,91, ...,</„}. Состояние q0 называется заключительным.
Управляющая головка — некоторое устройство, которое может перемещаться вдоль ленты так, что в каждый момент находится в определенной ячейке, или ’’обозревает” эту ячейку.
Механическое устройство, которое в зависимости от содержимого обозреваемой ячейки и состояния внутренней памяти может изменить состояние внутренней памяти и при этом либо изменить содержимое обозреваемой ячейки, либо сдвинуть управляющую головку в соседнюю ячейку слевы или в соседнюю ячейку справа. Если управляющая головка находится в крайней ячейке и должна сдвинуться в отсутствующую соседнюю ячейку, то машина пристраивает недостающую пустую ячейку.
Машинным словом машины Тьюринга (или конфигурацией) называется слово
aji а32 • • • *lajk • • •1
содержащее совокупность всех данных о состоянии машины в данный момент: арар . . . ар . . . ар — последовательность букв, записанных в ячейках ленты, ср — внутреннее состояние, к — номер обозреваемой ячейки.
Работа машины состоит в последовательном переходе от одной конфигурации к другой в результате выполнения одного из следующих действий:
Имея внутреннее состояние ср и обозревая ячейку, в которой записан символ ар машина переводит внутреннюю память в состояние ср и одновременно заменяет символ в обозреваемой ячейке на аг. Это
действие выражается командой
qiOj -> qsa
Имея внутреннее состояние q; и обозревая ячейку, в которой записан символ а^, машина переводит внутреннюю память в состояние qs и одновременно передвигает управляющую головку в соседнюю ячейку справа. Это действие выражается командой
qiQj -> qsR.
Имея внутреннее состояние q; и обозревая ячейку, в которой записан символ а^, машина переводит внутреннюю память в состояние qs и одновременно передвигает управляющую головку в соседнюю ячейку слева. Это действие выражается командой
qiQj -> qsL.
Совокупность всех команд, которые может выполнять машина, называется ее программой. Для каждого незаключительного внутреннего состояния q, и каждого символа aj из внешнего алфавита программа должна содержать ровно одну команду, начинающуюся с qiOj.
Выполнение каждой из команд может быть описано как процесс построения конфигурации nV по заданной конфигурации ш.
Пусть Е, Д — некоторые алфавиты, не содержащие символ ао, F — частичная «-местная функция, определенная на некотором подмножестве множества Е* всех слов в алфавите Е и со значениями в множестве Л*. Будем говорить, что данная машина Тьюринга вычисляет функцию F, если ее внешний алфавит включает алфавиты Е,Д и, каковы бы ни были слова ti,...,tn в алфавите Е, если значение F(ti, . . ., tn) определено, то эта машина перерабатывает конфигурацию giOriO . . . 0tn в конфигурацию 0 . . . ОдоОстО . . . О, причем F(ti,...,tn) = а, а если значение F(ti, . . ., tn) не определено, то в процессе переработки конфигурации giOriO . . . 0tn машина никогда не придет в заключительное состояние. Функция F называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая вычисляет функцию F.
Натуральные числа изображаются как слова в однобуквенном алфавите {|}, так что можно считать опрделенным понятие вычислимой по Тьюрингу частичной числовой функции.
Задачи
Построить машины Тьюринга, вычисляющие следующие функции:
s(t) = х + 1; 2) о(х^ = 0; 3) I^(xi, . . ., хп) = хт (1 < т < «); 4) х + у;
, Г х — 1, если х > 0;, fl, если х > 0;f 0, если х > 0;
) р^х) = 1„6) sg(T)= 1п7) sg(T)= 1
[0, если х = 0;7' 7[0, если х = 0;7' 7[ 1, если х = 0;
8)^) = о еслит<У 9)^-F 10) ¥ nHfL
Частично-рекурсивные функции
С помощью машин Тьюринга мы получили некоторое уточнение понятия вычислимой частичной функции из множества Е* в множество Д* для произвольных алфавитов Е и Д. В частности, мы имеем понятие вычислимой по Тьюрингу числовой функции, т. е. частичной многоместной функции из N в N. Посредством С(п) будем обозначать класс всех вычислимых по Тьюрингу частичных функций из Nn в N. Вместо С1) будем писать просто С.
Насколько хорошо понятие функции, вычислимой по Тьюрингу, соответствует интуитивному понятию вычислимой функции? В настоящее время известно много других формальных описаний вычислимых функций. Оказалось, что все они задают один и тот же класс «-местных вычислимых частичных числовых функций, совпадающий с С(п\ Кроме того, до сих пор никому не удалось привести пример вычислимой функции, которая не была бы вычислима по Тьюрингу. Это, а также многие другие наблюдения, позволили сформулировать следующий тезис, обычно называемый тезисом Чёрча: для любой вычислимой частичной функции из Е* в Д* существует машина Тьюринга, которая вычисляет эту функцию. В частности, интуитивно понимаемый класс «-местных вычислимых частичных числовых функций совпадает с С(п\ Заметим, что тезис Чёрча невозможно ни доказать, ни опровергнуть, так как понятие вычислимой функции не имеет строгого математического определения. Таким образом, тезис Чёрча — это своего рода естественно-научная гипотеза, подтверждаемая математическим опытом.
Классы С1-") (« = 1,2,.. .) допускают и другое, внутреннее описание, которое полезно знать всякому, кто изучает теорию алгоритмов.
Следующие тотальные (т. е. всюду определенные) числовые функции будем называть простейшими или базисными: s(x) = х + 1; о(х^ = 0; I^(xi, . . ., хп) = хт (1 < m < «). Очевидно, что все базисные функции вычислимы. Более того, решив задачи 1) -3) из раздела 2, мы доказали, что все они вычислимы по Тьюрингу.
Будем говорить, что «-местная (n > 1) частичная функция h получается с помощью операции подстановки из fc-местной функции / и «-местных функций yi, . . . ,yk, если для любых Xi, . . ., хп £ N имеет место условное равенство
Цхщ ...,х„)~ /(yi(®i, ...,x„Y---,gk($i,.. .,x„)Y
Например, функция f(x) = 1 получается операцией подстановки из функций в(ж) и o(xY Функция
/(ж, у, z) = 2 + 1
получается подстановкой из функций в(ж) и ll(x, у, z). Очевидно, что если функции f, yi, . . ., yk всюду определены, то h — тотальная функция. Кроме того, если функции f, yi, . . ., ук вычислимы, то и функция h вычислима.
Скажем, что (« + 1)-местная (« > 1) частичная функция h получается с помощью операции рекурсии из «-местной функции J и (« + 2)-местной функции у, если для любых Xi, . . ., хп, у £ N выполняются следующие условные равенства:
h^xx, . . •, хп, 0) 22 /(жх,. . ., xnY
Цх!,..., х„, у +1) ~ у(хх,. . ,,Хп,у, Цху, ...,х„,у)У
Для « = 0 операция рекурсии определяется следующим образом. Одноместная частичная функция h получается операцией рекурсии из двуместной частичной функции у и натурального числа а, если для любого натурального у выполняются условные равенства
/г(0) = а;
Цу+ 1) ~ у(у,Н(У^-
Например, функция h^x, у) = х-\-у получается рекурсией из функций 1}(х) и у(х, у, z) = z+1. Очевидно, что если функция h получается рекурсией из вычислимых функции f и у, то и функция h вычислима. Кроме того, если функции f и у всюду определены, то h — тотальная функция.
Функция называется примитивно репурсивной, если она может быть получена из базисных функций с помощью конечного числа применений операций подстановки и рекурсии. Иными словами, функция J является примитивно рекурсивной, если существует конечная последовательность функций Jo, . . ., fn, в которой каждая функция ft (г < «) либо является базисной, либо получается из каких-нибудь предшествующих функций с помощью подстановки или рекурсии, и при этом fn есть функция f. Как показывают приведенные выше примеры, функции f(x) = 1, у(х,у) = х + у являются примитивно рекурсивными. Из отмеченных выше свойств операций подстановки и рекурсии немедленно следует, что всякая примитивно рекурсивная функция вычислима и является тотальной.
Будем говорить, что «-местная (« > 1) частичная функция у получается с помощью операции минимизации (или p-оператора^ из (« + 1)-местной частичной функции f, если для любых Xi, . . ., хп, у £ N значение y(xi, . . ., жп) определено и равно у тогда и только тогда, когда для любого z < у значение /(жх, . . ., хп, z) определено и не равно 0, a /(жх, . . ., хп, у) = 0. В этом случае пишут
д($Ь . . ., хп) ~ ру(Дх!, . . ,,хп,у) = 0].
Заметим, что если функция у получается операцией минимизации из вычислимой функции f, то у также вычислима, однако она может оказаться не тотальной, даже если функция J всюду определена.
Функция называется частично-рекурсивной, если она может быть получена из базисных функций с помощью конечного числа применений операций подстановки, рекурсии и минимизации. Иными словами, функция J является частично-рекурсивной, если существует конечная последовательность функций, заканчивающаяся функцией f, в которой каждая функция либо является базисной, либо получается из предыдущих функций с помощью операций подстановки, рекурсии или минимизации. Тотальные частично-рекурсивные функции называются общерекурсивными.
Теорема 3.1. Класс всех п-местных частично-рекурсивных функций совпадает с классом С^п\
Эта теорема доказывается довольно рутинным способом. Мы этого делать не будем. Заметим лишь, что в силу тезиса Чёрча понятие частично-рекурсивной функции может рассматриваться как еще одно уточнение понятия вычислимой числовой функции.
Задачи
Доказать, что если функция /(ti, . . . ,жп) примитивно рекурсивна, то примитивно рекурсивна также функция дфсу, . . ., жп) = /(«<7(1), • • •, жст(п)), гДе с — произвольная тотальная функция из {1, ...,«} в
Доказать, что если функция /(ti, . . . ,жп) примитивно рекурсивна, то примитивно рекурсивна также функция Цху, . . .,хп, Т„+1) = f(_Xy, . . ,,хф.
Доказать, что следующие функции примитивно рекурсивны:
а) /(ж, у) = х • у; б) /(ж, у) = ху (здесь 0° = 1); в) /(ж) = ж! (здесь 0! = 1);
.,.fl,если х>0;,, ,f0,если х>0;,, ,fх — 1, еслих >0;
г) sg(T) =<д)sg(T)=<е)р(ж) =<
' v[ 0,если х=0;’’если х=0;'v[0, если х =0;
\\ I ж — у, если х > у, , ,,,,,,. ,,
ж а ж = < „— з ж — и ; и max у ; к mm у .
7 v 7{ 0, если х <у,717\\
Доказать, что следующие функции частично-рекурсивны:
а) х -у, б) ^; в) ^Т; г) |; д) [f]-
Машина с неограниченными регистрами
Рассмотрим еще одно уточнение интуитивного понятия алгоритма, работающего с натуральными числами.
Машина с неограниченными регистрами (МНР) — это своего рода идеализированный компьютер. МНР имеет бесконечно много регистров Ry, Ri, R3, . . ., в каждом из которых в любой момент времени записано некоторое натуральное число. Число содержащееся в регистре Rn, мы будем обозначать гп. Содержимое регистров может меняться при выполнении некоторой команды. Конечный список команд образует программу. Команды бывают следующих четырех типов:
Команда обнуления имеет вид ^(n) (n £ {1, 2, 3, . ..}). Выполнение такой команды заменяет содержимое регистра Rn на 0, не затрагивая другие регистры.
Команда прибавления единицы имеет вид S(n), где п £ {1, 2, 3, . ..}. Выполнение такой команды увеличивает содержимое регистра Rn на 1, не затрагивая другие регистры.
Команда переадресации имеет вид Т^т, п) (здесь тп,п Е {1, 2, 3, . ..}). Выполнение такой команды заменяет содержимое регистра Rn числом rm, содержащимся в регистре Rm, не затрагивая другие регистры (включая Rm).
Команда условного перехода имеет вид J(m, п, </) (m, п, q Е {1, 2, 3, . ..}). Выполнение такой команды состоит в следующем. Сравнивается содержимое регистров Rm и Rn. Если rm = гп, то машина переходит к выполнению </-й команды выполняемой программы; если rm ф тр, то машина переходит к выполнению следующей команды. Если требуется выполнение команды с номером, превосходящим число команд в программе, машина прекращает работу.
Команды обнуления, прибавления единицы и переадресации называются арифметическими.
Пусть п Е {1,2,3,...}. Каждую программу можно рассматривать как алгоритм с множеством возможных исходных данных Nn. Применение такого алгоритма к исходному данному (;z?i, . . ., х^ состоит в следующем. В начальный момент числа Ху, . . ., хп помещаются соответственно в регистры Ry, . . ., Rn, при этом во всех остальных регистрах содержится 0. Затем выполняются команды данной программы, начиная с первой. Один шаг работы алгоритма состоит в выполнении одной команды. Последовательность шагов работы алгоритма называется вычислением. Вычисление завершается, когда в программе нет команды, которую можно было бы выполнить. Это может произойти, если
выполнена последняя команда программы, и эта команда была арифметической;
при выполнении команды J(m, п,д) оказалось, что гт = тп, но q превосходит число команд в программе;
при выполнении команды J(m, п, </) оказалось, что гт ф тр, но это была последняя команда программы.
Завершение работы алгоритма всегда считается результативным. Результатом работы алгоритма является натуральное число, записанное в регистре Ry в момент завершения вычисления. Таким образом, каково бы ни было п Е {1,2,3,...}, каждая программа вычисляет частичную «-местную числовую функцию.
Частичная функция из Nn в N называется МНР-вычислимой, если существует программа для МНР, которая вычисляет эту функцию.
Примеры.
Функция /(ж, у) = ж + у вычисляется следующей программой:
^(3,2,5);
Щ);
S(3);
^(1,1,1).
Каково бы ни было п 6 {1, 2,3,.. .}, нигде не определенная функция из Nn в N вычисляется, например, следующей программой:
1) СП-
Задачи.
Доказать, что следующие функции МНР-вычислимы:
А ( А лА А к A А / если Ж = ^ A ft А J °’ еСЛИ ж < У- a sg ж ; б г ж = 5; в г ж, у = < 1, г г ж, у = < 1—
t П J \’7 J Vф если Ж ^ у; 7 7еСЛИ ж > у;
д) /(ж) = |; е) f(x) = [^] ([г] обозначает целую часть числа г).
Доказать, что если функция / вычисляется программой без команд условного перехода, то найдется такое число т, что либо (Уж)/(ж) = т, либо (Уж)/(ж) = ж + т.
Доказать, что для любой МНР-вычислимой функции существует программа без команд переадресации, вычисляющая эту функцию.
МНР-вычислимость частично-рекурсивных функций
Мы докажем, что всякая частично-рекурсивная функция вычислима на машине с неограниченными регистрами.
Соединение программ
В дальнейшем нам придется рассматривать программы, которые содержат другие программы в качестве подпрограмм. Рассмотрим некоторые технические средства, позволяющие строить сложные программы из более простых. Для этого нам понадобится некоторая стандартизация программ. Пусть программа Р состоит из команд Д, . . .,IS. Будем говорить, что программа Р имеет стандартный вид, если во всякой команде условного перехода J(m, n,q^ из Р выполняется неравенство q < s + 1. Очевидно, что каждая программа Р может быть приведена к стандартному виду путем замены в ней всякой команды вида J(m, n,q\ где q > s + 1 на J(m,n,s + 1), выполняющую точно такое же действие, а именно, остановку выполнения программы Р.
Пусть теперь Р = Д, . . ., Is и Q = Д, . . ., I't — программы стандартного вида. Соединением программ Р и Q называется программа
PQ — С^ • • • , Д Лз+11, С+t 1
где Д+1, . . ., Д+t — команды полученные из команд программы Q заменой каждой команды условного перехода J(m, n,g) на J(m, п, s + q). Очевидно, что результат выполнения программы PQ такой же, как и результат последовательного выполнения программ Р и Q. Можно говорить также о соединении трех и более программ, понимая, например, программу PQR как (PQ)R.
В том случае, когда одна программа используется как подпрограмма в другой программе, важно позаботиться о том, чтобы в ходе выполнения подпрограммы не изменилось содержимое регистров, используемых основной программой. Этого нетрудно добиться следующим образом. Пусть мы собираемся использовать программу Р как подпрограмму при составлении новой программы Q. Поскольку программа Р конечна, в ней используется конечное число регистров, так что найдется такое наименьшее число и (обозначим его р(РУ), что регистры Rd при и > и не используются в этой программе. Тогда при составлении программы Q, использующей Р в качестве своей части, т. е. подпрограммы, нужно использовать в качестве рабочих только регистры Rd при и > и.
Если программа Р предназначена для вычисления некоторой функции /(дц, . . ., xnY то, в соответствии с общими соглашениями, исходные данные записываются в регистры Ri, . . ., Rn, а результат — в регистр Ry. В тоже время, при использовании программы Р в качестве подпрограммы в другой программе, исходные данные для Р могут быть записаны в каких-то других регистрах RiT, . . -,Rin, а результат требуется поместить в регистр R. Чтобы обеспечить возможность такого использования программы Р, мы можем преобразовать ее в следующую программу, являющуюся соединением трех программ:
' Т(С,1);
Т(/„, п);
' Я(п + 1);
. z^PY;
р
{Т(1,/).
Модифицированную таким образом программу Р будем обозначать
Р[/1,
Реализация подстановки на МНР
Сейчас мы докажем, что класс всех МНР-вычислимых функций замкнут относительно операции подстановки.
Теорема 5.1. Пусть функция h(x), где х = (®i, . . ., xnY получена подстановкой из МНР-вычислимых функций f(yi, . . ., yk^ и У1 (х), . . ., дк^хф Тогда и функция й(х) МНР-вычислима.
Доказательство. Пусть программы F, Gi, . . ., Gk, имеющие стандартный вид, вычисляют соответственно функции f, gi, . . ., gk- Напишем программу Н для вычисления функции h. Пусть
т = шах(п, к, p(FY Р^Сф, • • •, p(GkYY
Тогда программа Н будет выглядеть как следующее соединение нескольких программ: Т(1,ш-Ц);
<. . .
Т^п, т + п);
Gi[m + 1, т + 2, . . ., т + п —> т + п + 1]
GkVm + l,m + 2,...,m + n —> т + п + к"\
F[m + п + 1, . . ., т + п + к 1]
Вспомнив только что введенные обозначения для модифицированных программ, читатель без труда убедится, что программа Н действительно вычисляет функцию h. Теорема 5.1 доказана.
Реализация рекурсии на МНР
Сейчас мы докажем, что класс всех МНР-вычислимых функций замкнут относительно операции рекурсии.
Теорема 5.2. Пусть функция h(x,yY где х = (®i, . . .,xnY получена рекурсией из МНР-вычислимых функций /(х) и g(x,y,z). Тогда и функция h(x,y) МНР-вычислима.
Доказательство. Пусть программы F и G, имеющие стандартный вид, вычисляют соответственно функции /(х) и g(x,y,zY Напишем программу Н для вычисления функции h(x,yY Пусть
т = шах(п + 2, p(FY p(G)).
Обозначим сумму т-\-п через t. Тогда программа Н будет выглядеть как следующее соединение нескольких программ:
Т(1,ш-Ц);
. . .
Т(п + 1, т + п + 1);
С[1,2,...,п ^/ + 3]
{Iq : J (t + 2, t + 1, p)
G[m+l,m + 2,...,m+n,/ + 2,/ + 3—>/ + 3]
^(1,1,-/);
. Ip + 3,1)
Вспомнив введенные выше обозначения для модифицированных программ, читатель без труда убедится, что программа Н действительно вычисляет функцию h. Теорема 5.2 доказана.
Реализация минимизации на МНР
Сейчас мы докажем, что класс всех МНР-вычислимых функций замкнут относительно операции минимизации.
Теорема 5.3. Пусть у(х) = py)f(x, у) = 0], где х = (®i, . . ., хп), а /(х, у) есть МНР-вычислимая функция. Тогда функция д(х) также МНР-вычислима.
Доказательство. Пусть программа F, имеющая стандартный вид, вычисляет функцию f(x,y). Напишем программу G для вычисления функции д(х). Пусть т = шах(п + l,p(F)). Тогда программа G будет выглядеть как следующее соединение нескольких программ:
' T(l,m+ 1);
<. . .
Т)п, т + п);
Jp :F[m+l,m + 2,...,m+n + l—>1]
(т. е. Jp является номером первой команды)
' J(l, т + п + 2, q);
S(m + п + 1);
_ Iq : T(m + п + 1, 1)
Вспомнив введенные выше обозначения для модифицированных программ, читатель без труда убедится, что программа G действительно вычисляет функцию д. Теорема 5.3 доказана.
Основной результат
Теорема 5.4. Всякая частично-рекурсивная функция является МНР-вычисдимой.
Доказательство. По определению, любая частично-рекурсивная функция может быть получена из базисных функций
о(х), s(x), I^(X1, . . ., хп)(п = 1, 2, . . .; 1 < т < п)
с помощью операций подстановки, рекурсии и минимизации. Базисные функции, очевидно, МНР-вычисли- мы. Так, функция о(х) вычисляется программмой, состоящей из одной команды
5(1),
функция s(t) вычисляется программмой, состоящей из одной команды
5(1),
а функция I^(xi, . . ., хп) вычисляется программмой, состоящей из одной команды
Т(т, 1).
Отсюда и из теорем 5.1-5.3 немедленно следует, что всякая частично-рекурсивная функция МНР-вычислима. Теорема 5.4 доказана.
Теорема 5.5. Всякая МНР-вычислимая функция является частично-рекурсивной.
Эта теорема доказывается более сложно с помощью такого рассуждения. Пусть функция /(х), где х = (a?i,. . ., хп), вычисляется программой Р. Обозначим через с(хД) содержимое регистра Ry после t шагов работы программы Р на исходных данных х, если она не завершилась раньше, и заключительное содержимое регистра Ry, если работа программы завершилась за < t шагов. Через j(x,t) обозначим номер
следующей команды после того как сделано ровно t шагов работы программы Р на исходных данных х, если она не завершилось раньше, и 0, если работа программы завершилась за < t шагов. Тогда, очевидно,
/(х) ~ с(х,цф'(хЭ) = 0]).
Затем доказывается, что функции с и j частично-рекурсивны. Это дает частичную рекурсивность функции /.
Таким образом, классы числовых функций вычислимых на машинах Тьюринга и на машинах с неограниченными регистрами, совпадают с классом всех частично-рекурсивных функций. Этот факт может рассматриваться как еще один довод в пользу тезиса Чёрча, в силу которого мы теперь имеем, что числовые функции, вычислимые в интуитивном смысле, — это в точности МНР-вычислимые функции.
Задачи
Составить программы для МНР, вычисляющие следующие числовые функции:
/(«, у, z) = х + у + г; 2) /(ж) = х\ (факториал); 3) /(ж, у) = х • у, 4) /(ж, у) = ху; 5) /(ж, у) = \х - у\;
/(ж, Z/) = max(z, у); 7) /(ж, у) = тш(т, у); 8) /(ж, у) = ^.
Нумерация вычислимых функций
Напомним, что N = {0, 1,2,.. .}. Пусть N+ = {1, 2, . . .}. Нетрудно убедиться, что функция
тг(т, п) = 2™ • (2n + 1) — 1
задает вычислимое взимно-однозначное соответствие между множествами N х N и N. Аналогично, функция ((т, п, у) = тг(тг(т — 1, п — 1), q — 1)
задает вычислимое взимно-однозначное соответствие между множествами N+ х N+ х N+ и N. Наконец, рассмотрим функцию
т^а^,..., ак^ = 2ai + 2ai+<12+1 + 2ai+a2+a3+2 + ... + 2ai+a2+ •+a'=+,c"1 - 1
(в дальнейшем вместо т^а^, . . ., a^)) мы будем писать просто т(ау, . . ., a^Y Функция т задает вычислимое взаимно-однозначное соответствие между множеством всех кортежей натуральных чисел и множеством N. Реально это соответствие устанавливается так. Для данного кортежа («1, . . ., а^ будем строить конечную последовательность нулей и единиц справа налево следующим образом. Первую единицу поставим на (ai + 1)- м месте справа, т. е пишем «1 нулей, а за ними — одну единицу. Вторую единицу поставим на (о2 + 1)-м месте влево от первой единицы, и так далее. Наконец, последнюю, fc-ю единицу поставим на (ак + 1)-м месте слева от (к — 1)-й единицы. Полученная последовательность нулей и единиц является двоичной записью некоторого положительного натурального числа а. Тогда а — 1 как раз и есть т(ау, . . ., а к). Пусть, например, дан кортеж (3, 7, 1). Тогда, по определению, т(3, 7, 1) = 23 + 211 + 213 — 1. Построим последовательность нулей и единиц, как сказано выше. Получим двоичное число 10100000001000, очевидно, равное числу 23 + 211 + 213. Вычитая из него 1, как раз и получаем т(3, 7, 1).
Используя функции тг и ф каждой команде I для МНР поставим в соответствие число /3(7) по следующему правилу:
/3(Z(n)) = 4(п - 1);
/3(5») = 4(п — 1) + 1;
/3(Т(т, п)) = 4тг(т — 1, п — 1) + 2;
/3(J(m, п, </)) = 4£(т, п, </) + 3.
Очевидно, функция /3 задает вычислимое взвимно-однозначное соответствие между командами для МНР и натуральными числами. Число /3(7) будем называть гёдедевым номером команды 7. Наконец, для любой программы Р = 71,72, • • •, 7S положим
7(P)=t(/3(71),...,/3(7s)).
Очевидно, что функция у задает вычислимое взаимно-однозначное соответствие между программами для МНР и натуральными числами. Число у(Р) будем называть гёдедевым номером программы Р или просто ее номером. Программу с номером п будем обозначать Рп.
Как известно, при любом n > 1 всякая программа для МНР вычисляет некоторую частичную «-местную числовую функцию, «-местную функцию, вычисляемую программой Ра, будем обозначать у),"'. Одноместную функцию, вычисляемую программой Ра, будем обозначать просто (ра.
Очевидно, что вычислимые числовые функции образуют счетное множество. Поскольку множество всех числовых функций имеет мощность континуума, очевидно существование невычислимых числовых функций. Теперь мы можем привести конкретный пример такой функции. Пусть
Уп^ + 1, если значение уп(п) определено; О, если значение уп(п) не определено.
Допустим, что эта функция вычислима. Тогда она МНР-вычислима. Пусть / вычисляется программой Рт, т. е. / есть (рт. Очевидно, что значение ym(m) определено, так что имеем:
.f(m) = ут(т) + 1 = /(т) + 1.
Это явный абсурд. Полученное противоречие доказывает, что на самом деле функция / невычислима.
Задачи.
Найти гёделев номер команды J(3,4,2).
Найти команду с номером 503.
Найти номер следующей программы:
Т(3,4);
5(3);
Z(l\
Найти программу Рюо.
., . Г ipn(nd + 27п, если <£>„(«) определено
Доказать, что невычислима функция t « = <9, ,.
( « , если уп(п) не определено
Пусть /(ж, у) — тотальная вычислимая функция. Для каждого т обозначим через дт такую функцию, что (Vy)gm(y) = /(m, у). Построить такую тотальную вычислимую функцию h, что (Vm)/z ф дт.
Теорема о параметризации
Условимся о некоторых терминах и обозначениях, связанных с функциями. В этой и следующих лециях мы будем рассматривать только числовые функции, т. е. многоместные частичные функции из N в N. Всюду определенные функции будем называть тотальными функциями.
Иногда функция задается путем выражения ее значений через значения аргументов в виде числовой формы. Например, говорят о функции ж2. Чтобы выражаться более аккуратно и различать числовые (и вообще, именные) формы и задаваемые ими функции, обычно используют так называемые А-обозначения. Например, упомянутую функцию ж2 можно обозначить так: Ат.ж2. Вообще, если дана именная форма f(x) с единственным параметром х, то выражение Хх.f(x) считается именем (т. е. обозначением) функции, которая каждому значению а переменной х сопоставляет значение /(а) формы f(x) при этом значении переменной х. В выражении Хх. f(x) переменная х оказывается связанной. Если именная форма f(x, у) наряду с х содержит другие параметры из списка у, то выражение Хх. f(x, у) является функциональной формой с параметрами у, значением которой при данных значениях а параметров у является функция Хх.f(x, а). Аналогично вводятся обозначения для многоместных функций. Пусть дана именная форма Дад, . . ., тп) с параметрами ад, . . ., хп. Тогда выражение Аад . . ,xn.f(xi, . . ., хп) считается обозначением п- местной функции, которая каждому набору ау, . . . ,ап значений переменных ад, . . ., хп сопоставляет объект, именем которого является выражение Дед, . . ., a„Y Если именная форма Дад, . . ., хп, у) наряду с ад, . . ., хп содержит другие параметры из списка у, то выражение Аад . . ,xn.f(xi, . . ,,хп,у) является функциональной формой с параметрами у, значением которой при данных значениях а параметров у является функция
А а- . . . хп .ф^х-^, . . ., хп, а).
Теорема 7.1 (теорема о параметризации). Пусть f — двуместная вычислимая функция. Существует одноместная тотальная вычислимая функция к такая, что f(x,y) ~ Ук^фуУ
Доказательство. Пусть программа F вычисляет функцию /. Для каждого х построим программу Q^, являющуюся соединением двух программ:
Т(1, 2);
5(1);
S(i);
5(1) F,
где команда 5(1) написана х раз. Пусть кДД — гёделев номер программы Q$. Очевидно, что функция к вычислима. Нетрудно видеть, что программа Q^ вычисляет функцию Xy.f(x,y), т. е. имеет место
/(ж, у) ~ ^W(;/),
что и требовалось доказать. Теорема 7.1 доказана.
Только что доказанная теорема имеет следующее естественное обобщение.
Теорема 7.2 (s-m-n-теорема). Для любых т, п > 1 существует тотальная вычислимая (т + Д-местная функция s™ такая, что для любых натуральных чисел е, ад, . . ., хт, yi, . . . ,уп имеет место
ДД^Дх!,. ..,Хт,У!,. ,.,уД~(У1, . -.,уД.
Эта теорема имеет прозрачный смысл: по программе с гёделевым номером е, вычисляющей (т + п)-
местную функцию Дет+п\ и произвольному набору натуральных чисел ад, . . ., хт можно найти (с помощью функции s™) гёделев номер программы, вычисляющей функцию
Др .. .уп.Дд+^Дх, • • • ,xm,yi,..., уД.
Теорема доказывается с помощью того же программистского приема, что и теорема о параметризации.
Универсальная вычислимая функция
Пусть К. — некоторый класс «-местных (n > 1) функций. Тогда (п + 1)-местная функция U называется универсальной для класса К., если выполнены следующие условия:
для каждого натурального е функция Аад . . ,xn.U(e, х^, . . ., хД принадлежит классу /С;
для любой функции f из класса К. существует такое натуральное число е, что
f — А./- ... хп.U Д, х^,..., хД.
Очевидно, что универсальная функция для класса К. существует в том и только в том случае, когда класс К. не более чем счетен. Более интересен вопрос о существовании вычислимых универсальных функций для классов, состоящих только из вычислимых функций.
Теорема 8.1 (существование вычислимой универсальной функции). Для любого натурального числа п > 1 существует (n +1)-местная вычислимая функция, универсальная для класса С1'"'1 всех п-местных вычислимых функций.
Доказательство, (п + 1)-местную функцию ф(п) определим как Аеад . . . xn.<pen\xi, . . . ,хД. Функция ф(п) вычисляется следующим неформальным алгоритмом:
’’Пусть даны натуральные числа е, ад, . . ., хп. Найдите программу Ре с номером е. Затем поместите в регистры Д1, . . ., Rn соответственно числа ад, . . ., хп и запустите выполнение программы Ре. Если вычисление заканчивается, требуемое значение Ф^^е, ад, . . ., хД содержится в регистре Д1.”
Таким образом, функция ф(п) вычислима.
Докажем, что ф(п) — универсальная функция для класса С1-"). Действительно, для любого натурального е функция А®1 . . . т^.Ф^^е, ад, . . ., хД совпадает с функцией ре и, следовательно, принадлежит классу С1-'1). С другой стороны, любая функция / из класса С1-") вычисляется некоторой программой Ре и потому имеет вид ре для некоторого е. Но тогда, очевидно, / = Аад . . . т^.Ф^^е, ад, . . . ,хД. Теорема доказана.
Задачи.
Доказать, что не существует вычислимой функции, универсальной для класса всех одноместных тотальных вычислимых функций.
Доказать, что существует вычислимая функция, универсальная для класса всех одноместных примитивно-рекурсивных функций.
Доказать, что не существует примитивно-рекурсивной функции, универсальной для класса всех одноместных примитивно-рекурсивных функций.
Доказать, что существует общерекурсивная функция, не являющаяся примитивно рекурсивной.
Разрешимые и перечислимые множества
Пусть X — некоторый ансамбль конструктивных объектов, А — его подмножество. Характеристической функцией множества А называется функция ха : X —> {0, 1}, определяемая следующим образом:
. fl, если х G А;
Ха(х) = 1 пд
Определение. Множество А С X называется разрешимым (или рекурсивным), если его характеристическая функция ха вычислима.
Иными словами, множество А разрешимо, если существует алгоритм, который для каждого х £ X вычисляет истинностное значение высказывания х Е А. Очевидно, что множества X и 0 разрешимы.
Теорема 9.1. Если множества А, В С X разрешимы, то множества AU В, АП В, А \ В разрешимы.
Доказательство. Доказываемое утверждение совершенно очевидно. Действительно, так как множества А, В С X разрешимы, то их характеристические функции ха и хв вычислимы. Тогда функция ХАив вычисляется следующим алгоритмом: ’’если Ха($) = 1 и Хв($) = 1, то Xaub($) = 1; в противном случае ХАив($) = 0”. Аналогично находятся значения Хапв($) и Ха\в(ж), если найдены значения Ха($) и Хв(т). Теорема доказана.
Из теоремы 9.1, в частности, получается, что дополнение X \ А разрешимого множества А разрешимо.
Полухарактеристической функцией множества А называется частичная функция фд из А в {1}, определяемая следующим образом:
, , fl, если х Е А;
I не определено, еслит^А.
Определение. Множество А С X называется полуразрешимым, если его полухарактеристическая функция фд вычислима.
Теорема 9.2. Всякое разрешимое множество полуразрешимо.
Доказательство. Пусть множество А С X разрешимо. Тогда его характеристическая функция ха вычислима. Полухарактеристическая функция фд множества А вычисляется следующим неформальным алгоритмом: ’’Пусть дан элемент х Е X. Вычислить ха($)- Если Ха($) = 1, то положить фд(х) = 1; в противном случае значение фд(х) не определено.” Теорема доказана.
Теорема 9.3 (теорема Поста). Множество А С X разрешимо тогда и только тогда, когда оба множества А и X \ А полуразрешимы.
Доказательство. Если множество А разрешимо, то множество X \ А также разрешимо, и по теореме 9.2 оба они полуразрешимы.
Обратно, пусть оба множества А и АДА полуразрешимы. Тогда их полухарактеристические функции фд и фх\А вычислимы. Характеристическая функция ха множества А вычисляется следующим неформальным алгоритмом: ’’Пусть дан элемент х Е X. Запустить параллельное выполнение программ для вычисления значений фд(х) и Фх\а(ж)- Если первая программа выдала результат, то Ха($) = 1- Если вторая программа выдала результат, то Ха($) = 0. Теорема доказана.
Последовательностью называется любая функция, область определения которой — множество всех натуральных чисел N. Следующее понятие в некотором смысле является алгоритмическим аналогом понятия не более чем счетного множества.
Пусть X — некоторый ансамбль конструктивных объектов. Множество А С X называется перечислимым (или рекурсивно перечислимым), если А = 0 или А является множеством значений некоторой вычислимой последовательности.
Теорема 9.4. Всякое перечислимое множество полуразрешимо.
Доказательство. Пусть множество А С X перечислимо. Если Л = 0, то Л разрешимо и, следовательно, полуразрешимо. Пусть Л ^ 0. Тогда А является множеством значений некоторой вычислимой последовательности / : N —> X. Полухарактеристическая функция Фа множества А вычисляется следующим неформальным алгоритмом: ’’Пусть дан элемент х Е X. Для каждого натурального п, начиная с О, вычислять f(n) и проверять условие f(n) = х. Если нашлось такое п, что f(n) = х, то фд(х) = 1.” Теорема доказана.
Пусть X и У — некоторые ансамбли конструктивных объектов, / — частичная функция из X в У. Графиком функции /называется множество Гу С X х У, определяемое следующим образом:
Г/ = ^гуАу = fMY
Теорема 9.5 (теорема о графике). Частичная функция f из X в У вычислима тогда и только тогда, когда ее график Г у перечислим.
Доказательство. Пусть f — частичная вычислимая функция из X в У. Если функция f нигде не определена, то ее график пуст и, следовательно, перечислим по определению. Рассмотрим случай, когда f определена хотя бы в одной точке. Пусть f определена в точке а Е X. Тогда пара (□,/(□)) принадлежит графику Гу. Будем считать, что фиксировано некоторое кодирование ансамбля конструктивных объектов X натуральными числами, т. е. фиксирована некоторая вычислимая биекция а : X —> N. Для каждого натурального числа г положим х< = а-1 (г). Последовательность у : N —> X х У определим следующим образом. Пусть дано натуральное число п. Оно является номером некоторой пары натуральных чисел Д, г) при рассмотренной нами нумерации всех пар натуральных чисел т, т. е. т(1, г) = п, причем числа I и г можно эффективно вычислить по п. Запустим алгоритм вычисления функции f на исходном данном Х[ и дождемся выполнения г + 1 шагов работы этого алгоритма. Если за г + 1 шагов или раньше получен результат ф(хф, полагаем д(п) = (ж;, ф)хф). Если же за г + 1 шагов работа алгоритма еще не завершилась или же произошла безрезультатная остановка, полагаем д)п) = (□,/(□)). Очевидно, что последовательность д вычислима. Очевидно также, что множество ее значений Ran(g) является подмножеством графика Гу. Докажем, что Гу С Ran(g). Пусть пара фк, у) принадлежит графику функции f. Это означает, что алгоритм вычисления функции f на исходном данном х заканчивает работу, скажем, за г > 0 шагов и выдает результат у. Пусть а(ж) = /. Положим п = т(/, г — 1). Из определения функции д видно, что д(п) = (ж, у), т. е.
(ж, у) Е Ran(f).
Таким образом, график функции f является множеством значений вычислимой последовательности д, следовательно, он перечислим по определению.
Пусть график Г у функции f перечислим. Если он пуст, то функция f нигде не определена и, следовательно, вычислима. Если же график не пуст и перечислим, то он является множеством значений некоторой вычислимой последовательности д : N —> X х У. Функция / вычисляется следующим алгоритмом. Пусть дано натуральное число п. Последовательно для каждого натурального г, начиная с 0, вычисляем значение дф) = (□,/(□)) и проверяем условие а = п. Если это условие выполнено, то f(n) = f(a), и вычисление закончено. Теорема доказана.
Теорема 9.6. Пусть f — частичная вычислимая функция из X в У. Тогда ее область определения Dom(f) С X и множество значений Ran(f) С У суть перечислимые множества.
Доказательство. Пусть функция f вычислима. По теореме 9.5 ее график перечислим. Если f нигде не определена, то Dom(f) и Ran(f) пусты и, следовательно, перечислимы. В противном случае Гу является множеством значений некоторой вычислимой последовательности g : N —> X х У. Последовательности d : N —> JC и г : N —>У определим следующим образом. Пусть дано натуральное число п. Вычисляем
и полагаем (Цп) = а, гфф = Ь. Очевидно, что последовательности d и г обе вычислимы, причем Ran(d) есть в точности множество первых компонент пар из Гу, т. е. область определения фунции f, a Ran^r) — это в точности множество вторых компонент пар из Гу, т. е. множество значений функции f. Таким образом, множество Dom(f) является множеством значений вычислимой последовательности d и перечислимо по определению. Множество Ran(f) является множеством значений вычислимой последовательности г и потому также перечислимо. Теорема доказана.
Теорема 9.7. Множество А С X перечислимо тогда и только тогда, когда оно является множеством значений некоторой вычислимой функции.
Доказательство. Пусть множество А перечислимо. Докажем, что А является множеством значений некоторой вычислимой функции. Если оно пусто, то является множеством значений нигде не определенной функции. Если же А не пусто, то, по определению, оно является множеством значений вычислимой посдедовательности, и утверждение доказано.
Обратно, если А является множеством значений некоторой вычислимой функции, то по теореме 9.6 оно перечислимо. Теорема доказана.
Теорема 9.8. Множество А С X перечислимо тогда и только тогда, когда оно является областью определения некоторой вычислимой функции.
Доказательство. Пусть множество А перечислимо. Тогда, по теореме 9.4, оно полуразрешимо. Следовательно, его полухарактеристическая функция фд вычислима. Но всякое множество является областью определения своей полухарактеристической функции. Таким образом, А является областью определения вычислимой функции фд.
Обратно, если множество А является областью определения некоторой вычислимой функции, то по теореме 9.6 оно перечислимо. Теорема доказана.
Теорема 9.9. Всякое полуразрешимое множество перечислимо.
Доказательство. Полуразрешимое множество А является областью определения вычислимой функции фд и по теореме 9.6 перечислимо. Теорема доказана.
Теорема 9.10. Пусть X — произвольный ансамбль конструктивных объектов, А — произвольное его подмножество. Тогда следующие условия эквивалентны;
множество А перечислимо;
множество А полуразрешимо;
множество А является областью определения некоторой вычислимой функции;
множество А является множеством значений некоторой вычислимой функции.
Доказательство. Эквивалентность условий 1) и 2) вытекает из теорем 9.4 и 9.9. В силу теорем 9.8 и 9.7 каждое из условий 3), 4) эквивалентно условию 1). Теорема доказана.
Теорема 9.11. Пусть X — произвольный ансамбль конструктивных объектов, А, В С X — перечислимые множества. Тогда множества АПВ и Ли В перечислимы.
Доказательство. Пусть А, В С X — перечислимые множества. Докажем перечислимость множества ЛиВ. Если хотя бы одно из множеств А, В пусто, то ЛиВ совпадает с другим множеством и потому перечислимо. Рассмотрим случай, когда оба множества А, В непусты. Тогда А является множеством значений некоторой вычислимой последовательности f, а В — множеством значений некоторой вычислимой последовательности у. Определим последовательность h следующим образом: для любого натурального числа п положим
х ( если п четно;
1
I y\—Q—), если п нечетно.
Очевидно, что последовательность h вычислима, а множество ее значений есть в точности множество Ли В.
Докажем, что множество ЛАВ перечислимо. Для этого достаточно доказать, что оно полуразрешимо. Множества А, В полуразрешимы, следовательно, их полухарактеристичекие функции фд и фв вычислимы. Полухарактеристическая функция фдпв множества А П В вычисляется следующим алгоритмом. Пусть дан элемент х Е X. Вычислять фдфсф Если вычисление завершилось результативно, вычислять фв^хф Если и это вычисление завершилось результативно, то ^лпв(ж) = 1- Теорема доказана.
Задачи.
Доказать, что существует множество натуральных чисел, не являющееся перечислимым.
Доказать, что бесконечное множество А С N разрешимо тогда и только тогда, когда А является множеством значений строго возрастающей тотальной вычислимой функции.
Доказать, что непустое множество А С N разрешимо тогда и только тогда, когда А является множеством значений монотонно (не обязательно строго) возрастающей тотальной вычислимой функции.
Теоремы о разрешимых и перечислимых множествах
Функция / : N —> N называется неубывающей, если
Y^x,yYx <у^ f^ < /(у)].
Будем говорить, что множество А С N перечислимо в порядке неубывания, если существует такая неубывающая вычислимая функция / : N —> N, что А = Ran(JY
Теорема 10.1. Пусть А С N. Множество А разрешимо и непусто тогда и только тогда, когда оно перечислимо в порядке неубывания.
Доказательство. Пусть множество А С N разрешимо и непусто. Пользуясь разрешимостью множества А, найдем его наименьший элемент пу. Теперь определим функцию / : N —> N следующим образом:
/(0) = «о;
Дт + 1) = |Дт + 1) = |х + 1, если х + 1 G А, f(xY в противном случае.
Дт + 1) = |
Дт + 1) = |
Нетрудно убедиться, что J — неубывающая вычислимая функция, и
А = Ran(JY
Обратно, пусть существует такая неубывающая вычислимая функция / : N —> N, что А = Ran(JY Очевидно, что в этом случае А непусто. Если множество А конечно, то оно, очевидно, разрешимо. Если же А бесконечно, то для выяснения вопроса, принадлежит ли произвольное данное число х множеству А, будем вычислять последовательные значения /(0), /(1), /(2), . . . функции J, пока среди них не появится число, большее, чем х. Если к этому моменту число х уже появилось среди значений функции J, то х £ А; в противном случае х ^ А. Итак, мы располагаем алгоритмом для распознавания принадлежности произвольного числа множеству А, т. е. А разрешимо. Теорема 10.1 доказана.
Функция / : N —> N называется возрастающей, если
Y^x,yYx <у^ f(x) < /(у)].
Будем говорить, что множество А С N перечислимо в порядке возрастания, если существует такая возрастающая вычислимая функция / : N —> N, что А = Ran(JY
Теорема 10.2. Пусть А С N. Множество А разрешимо и бесконечно тогда и только тогда, когда оно перечислимо в порядке возрастания.
Доказательство. Пусть множество А С N разрешимо и бесконечно. Пользуясь разрешимостью множества А, найдем его наименьший элемент пу. Теперь определим функцию / : N —> N следующим образом:
/(0) = «о;
/(ж + 1) = ру^у G Akf^ < yY
Нетрудно убедиться, что J — тотальная возрастающая вычислимая функция, и Л = Ran(JY
Обратно, пусть существует такая возрастающая вычислимая функция / : N —> N, что А = Ran(JY Очевидно, что в этом случае множество А бесконечно. Для выяснения вопроса, принадлежит ли произвольное данное число х множеству А, будем вычислять последовательные значения /(0), /(1), /(2), . . . функции J, пока среди них не появится число, большее, чем х. Если к этому моменту число х уже появилось среди значений функции J, то х 6 А; в противном случае х ^ А. Итак, мы располагаем алгоритмом для распознавания принадлежности произвольного числа множеству А, т. е. А разрешимо. Теорема 10.2 доказана.
Теорема 10.3. Всякое бесконечное перечислимое множество содержит бесконечное перечислимое подмножество.
Доказательство. Пусть множество Л С N перечислимо и бесконечно. Тогда, по определению, Л является множеством значений некоторой вычислимой последовательности f. Определим функцию д следующим образом:
fl(0)=/(0);
Дж + 1) = HpyVHy') > ^Д)])-
Нетрудно убедиться, что д — тотальная возрастающая вычислимая функция. Положим В = Ran(gY По теореме 10.2 множество В разрешимо. Так как при этом, очевидно, В С Л, то теорема 10.3 доказана.
Нумерация перечислимых множеств
Как было доказано в разделе 9, каждое перечислимое множество является областью определения некоторой вычислимой функции. Это позволяет задать следующую нумерацию всех перечислимых подмножеств N. Пусть ИЛ = Dom(pxY Число ж будем называть гёделевым номером множества ИД. Очевидно, что всякое перечислимое множество имеет бесконечно много гёделевых номеров.
В разделе 9 было также установлено, что каждое перечислимое множество является множеством значений некоторой вычислимой функции. Используя нумерацию перечислимых множеств, этот факт можно выразить в следующей более сильной форме.
Теорема 11.1. Существует одноместная тотальная вычислимая функция f такая, что для любого х Dom^px) = Ran^pj^Y
Доказательство. Пусть двуместная функция h определена следующим образом:
а = Г у, если ДДу);
' ’[ не определено в противном случае.
Очевидно, что функция h вычислима. По теореме о параметризации (раздел 7) существует такая одноместная тотальная вычислимая функция f, что h^x, у) ~ рдх^у) для любых х, у. Из этого условного равенства и определения функции h следует, что у £ Ran(p^xY <=>ДДу) <^уЕ Dom^pxY Это как раз и означает, что / — искомая функция. Теорема 11.1 доказана.
Неразрешимые алгоритмические проблемы
Пусть / — частичная функция. Функция g называется продолжением функции f, если Dom(f^ С Dom^ и у (ж) = f(x) для любого х £ Dom^fY
Теорема 12.1. Существует частичная вычислимая функция, не имеющая тотального вычислимого продолжения.
Доказательство. Рассмотрим следующую частичную функцию / из N в N:
. . Г yn(n) + 1, если значение уп(п) определено;
' I не определено, если значение pn^ не определено.
Очевидно, что функция f вычислима. Докажем, что никакая тотальная вычислимая функция не является продолжением функции f. Пусть дана произвольная тотальная вычислимая функция у : N —> N, и пусть т — гёделев номер программы, вычисляющей функцию у. Тогда у = рт, и
g(m) = pm(mY(1)
Так как значение ym(m) определено, то
/(т) = рт^т) + 1.(2)
Равенства (1) и (2) показывают, что функция у не является продолжением функции f. □
Теорема 12.2. Существует неразрешимое перечислимое множество.
Доказательство. В силу теоремы 12.1 существует частичная вычислимая функция /, не имеющая тотального вычислимого продолжения. Область определения этой функции Dom(f^ — перечислимое множество. Докажем, что оно неразрешимо. Это вытекает из следующего довольно очевидного общего факта: если область определения частичной вычислимой функции разрешима, то эта функция имеет тотальное вычислимое продолжение. Действительно, пусть д — вычислимая частичная функция из X в У, причем множество Вот(д) С X разрешимо. Рассмотрим тотальную функцию h : X —> У, определенную следующим образом: для любого х £ X
,, \ _ 1 д($У если х 6 Вот(дУt 0, если х ^ Вот^дУ
Очевидно, что функция h вычислима и является продолжением функции д. □
Теорема 12.3. Множество К = {п|уп(п) определено^ перечислимо, но не разрешимо.
Доказательство. Множество К является областью определения функции f, построенной при доказательстве теоремы 12.1. Его неразрешимость была установлена при доказательстве теоремы 12.2. □
Теорема 12.3 означает алгоритмическую неразрешимость так называемой проблемы самоприменимости программ: не существует алгоритма, который по любой программе для МНР давал бы правильный ответ на вопрос, завершается ли работа этой программы, когда исходным данным является гёделев номер этой программы. Очевидно, что это явление характерно не только для МНР, но и для любого другого способа программирования.
Теорема 12.4 (неразрешимость проблемы остановки). Не существует алгоритма, который по любой программе Р для МНР и любому исходному данному х давал бы правильный ответ на вопрос, завершается ли работа программы Р на исходном данном х.
Доказательство. Если бы существовал алгоритм, о котором идет речь в формулировке теоремы, то, очевидно, была бы разрешима проблема самоприменимости программ, что, как мы видели, невозможно. □
Теорема Райса
Проблема самоприменимости и проблема остановки — это лишь два примера неразрешимых алгоритмических проблем в теории алгоритмов. На самом деле оказывается неразрешимой любая нетривиальная алгоримическая проблема, связанная с распознаванимем свойств вычислимых функций по программам, вычисляющим эти функции.
Пусть У — произвольное семейство одноместных частичных числовых функций, т. е. У С С. Индексным множеством семейства У называется множество 1^ = {n|yn 6 УУ Иными словами, индексное множество семейства У состоит в точности из всех номеров программ, вычисляющих функции из семейства У. Семейство УСС называется нетривиальным, если У ф 0 и У ф С.
Теорема 13.1 (теорема Райса). Индексное множество 1^ всякого нетривиального семейства функций УСС неразрешимо.
Доказательство. Пусть ^ — нигде не определенная функция. Допустим, что ( £ 7. Так как семейство У нетривиальное, существует функция g £ С \ У. Двуместную частичную функцию / определим следующим образом: для произвольных натуральных чисел п и х положим
„,, Г д(хУ если уп(п) определено;
— I не определено, если pn^ не определено.
Функция f вычисляется следующим неформальным алгоритмом:
’’Вычислять рп(пУ Если будет получен результат, перейти к вычислению д(хУ Если вычисление завершится результативно, положить f(n, х) = д(хУ”
В силу теоремы о параметризации существует одноместная тотальная вычислимая функция к такая, что f(n,x) ~ Рк^пУ^У Очевидно, что если п £ К, т. е. значение уп(п) определено, то Рк^ = 9, и к^п^ ^ 1т. Если же п у. К, т. е. значение уп(п) не определено, то Рк^ = У и к(п) £ М. Таким образом,
п Е К ЕР к(п) ^ 1^.(3)
Из условия (3) непосредственно вытекает, что если бы множество 1т было разрешимым, то разрешимо было бы и множество К, что невозможно в силу теоремы 12.3.
Мы доказали неразрешимость множества 1^ при условии, что ^ £ 7. Если же ^ ^ Т, то из доказанного вытекает неразрешимость множества Ic\r = N \ Ij, откуда уже следует неразрешимость множества 1^, так как дополнение неразрешимого множества неразрешимо. □
Десятая проблема Гильберта
Мы видим, что в теории алгоритмов имеется очень много неразрешимых алгоритмических проблем. Используя результаты о неразрешимости некоторых проблем в теории алгоритмов, удалось доказать алгоритмическую неразрешимость некоторых проблем, имеющих общематематическое значение.
В 1900 году на Международном математическом конгрессе в Париже знаменитый немецкий математик Д. Гильберт сформулировал ряд математических проблем, решение которых, по его мнению, наиболее актуально для математики 20-го века. Одна из них, под номером 10, касалась так называемых диофантовых уравнений, т. е. уравнений вида
р(®1, ®2, • • • , Жп) = О,
где р(®1, «2, • • •, ®п) — диофантов многочлен, т. е. многочлен от переменных Ху, Х2,..., хп с целыми коэффициентами, причем ищутся только целые решения такого уравнения. Десятая проблема Гильберта состояла в том, чтобы установить, существует ли алгоритм, с помощью которого можно определить, имеет ли решение произвольное наперед заданное диофантово уравнение. В 1970 году советский математик Ю. В. Матиясевич доказал, что такого алгоритма не существует. Суть его доказательства состоит в том, что для любого перечислимого множества А С N можно написать такой диофантов многочлен р^а, Xi, Х2, . . ., хп) от переменных a, Xi, Х2, . . ., хп, что для любого натурального а уравнение р(а, Xi, Х2, . . ., хп) = 0 как уравнение относительно неизвестных Xi, Х2, . . ., хп имеет целые решения тогда и только тогда, когда a £ А. Теперь решение десятой проблемы Гильберта непосредственно вытекает из существования неразрешимого перечислимого множества.
Задачи.
Пусть тотальная одноместная вычислимая функция / : N —> N удовлетворяет условию (Уж)/(ж) > х. Доказать, что множество значений Ran(f^ функции / разрашимо.
Доказать, что каждое бесконечное перечислимое множество А С N является множеством значений некоторой взаимно-однозначной тотальной вычислимой функции / : N —> N.
Доказать, что график тотальной вычислимой функции разрешим.
Доказать, что полный прообраз /-1(Л) разрешимого множества А относительно тотальной вычислимой функции / разрешим.
Пусть А С N — разрешимое множество, / : N —> N — тотальная вычислимая функция, причем Ran(f^ = N, /(Д) П /(N \ Л) = 0. Доказать, что множество /(Л) разрешимо.
Пусть А, В — перечислимые множества, С — разрешимое множество, причем ЛАВ = 0, А С С С ЛиВ. Доказать, что множество А разрешимо.
Пусть А — произвольное семейство перечислимых множеств натуральных чисел. Индексным множеством семейства А называется множество 1д = {п|ИД G Д}. Семейство А называется нетривиальным, если оно не пусто и содержит не все перечислимые множества натуральных чисел. Доказать следующий вариант теоремы Райса для перечислимых множеств: индексное множество 1д всякого нетривиального семейства перечислимых множеств А неразрешимо.
Индексы разрешимых и конечных множеств
Каждое разрешимое, в частности, каждое конечное множество перечислимо, следовательно, имеет вид ИД для некоторого х. Дополнение разрешимого множества также разрешимо, следовательно, перечислимо. Однако, как мы сейчас увидим, гёделев номер дополнения разрешимого множества ИД не может быть найден по числу х с помощью какого-либо алгоритма.
Теорема 15.1. Не существует частичной вычислимой функции -^ такой, что
(Уж)[И4 разрешимо => ф-У^х) ^ W^^ = Жг)].
Доказательство. Предположим, что такая функция ^ существует. Рассмотрим двуместную функцию
/(ж, у) ~ рЛхф
Очевидно, что функция / вычислима. По теореме о параметризации существует одноместная тотальная вычислимая функция у такая, что /(ж, у) ~ рд^(у") для любых х, у. Из этого условного равенства и определения функции f следует, что
_ Г N, если х Е К;^х^[ 0, если х ^ К.
Таким образом, для любого х множество Wg^) разрешимо. Тогда при любом х определено значение ^(у(®)), причем
__._ С 0, если х Е К;
У^^У [ N, если х ^ К.
Значит, К = {«(Жр^^) ^ 0}. Так как множество К перечислимо, но не разрешимо, то по теореме Поста его дополнение неперечислимо. С другой стороны, множество {ic^p^^p ф 0} перечислимо. Действительно, оно полуразрешимо, так как его полухарактеристическая функция вычисляется следующим неформальным алгоритмом: ’’Пусть дано число х. Вычислить ф(у(хУ). Найти программу с номером ф(у(хУ и запустить параллельные вычисления этой программы на исходных данных 0,1,2,.... Если какое-то из этих вычислений завершилось результативно, выдать 1.” Полученное противоречие показывает, что на самом деле вычислимой функции ф не существует. Теорема 15.1 доказана.
По определению, множество разрешимо тогда и только тогда, когда вычислима его характеристическая функция. Гёделев номер характеристической функции ха разрешимого множества Л С N будем называть характеристическим индексом множества А.
Теорема 15.2. Существует вычислимая функция h : N —> N такая, что для любого х, если рж — характеристическая функция некоторого множества А, то Ph(x) — характеристическая функция его дополнения N\ А.
Доказательство. Двуместную частичную функцию f определим следующим образом:
/(ж, у) ~ sg(^(y)).
Очевидно, что функция f вычислима. По теореме о параметризации существует такая одноместная тотальная вычислимая функция h, что f(x,y) ~ Рп^фу) Для любых х,у. Из этого условного равенства и определения функции f следует, что рц^УТ) — 8§(Рх(уУ- В частности, если у.,. — характеристическая функция некоторого множества А, то рцх) — характеристическая функция его дополнения N \ Л, что и требовалось доказать. Теорема 15.2 доказана.
Следующая теорема показывает, что существует алгоритм, который по характеристическому индексу разрешимого множества А находит его гёделев номер как перечислимого множества.
Теорема 15.3. Существует вычислимая функция у : N —> N такая, что для любого х, если рх — характеристическая функция некоторого множества А, то Wg^) = А.
Доказательство. Двуместную частичную функцию f определим следующим образом:
Г 1, если рДу) = 1;
' ’ [не определено в противном случае.
Очевидно, что функция f вычислима. По теореме о параметризации существует такая одноместная тотальная вычислимая функция у, что
7<Х ?/) ~ ^дф)(у)
для любых х, у. Из этого условного равенства и определения функции / следует, что Wg^) = {у|уя7(у) = 1}- Таким образом, если рх — это характеристическая функция некоторого множества А, то Wg^) = А, что и требовалось доказать. Теорема 15.3 доказана.
Оказывается, однако, что обратный переход — от гёделевых номеров разрешимых множеств к их характеристическим индексам — невозможно осуществить с помощью какого-либо алгоритма.
Теорема 15.4. Не существует одноместной частичной вычислимой функции ф такой, что
(Уж)[И4 разрешимо => (!ф> (ж) & ^(ж) = Хир]-
Доказательство. Допустим, что такая функция ф существует. Для каждого х положим
-ф^ ~ дфгф#фхЖ
где у и h — функции, существование которых утверждается соответственно в теоремах 15.3 и 15.2. Оче- идно, что функция ф вычислима. Тогда, если х — гёделев номер разрешимого множества А, то ффхф — характеристический индекс множества А, а Ифффсф — характеристический индекс его дополнения N \ А. Наконец, V'M есть гёделев номер множества N\ А. Таким образом, с помощью вычислимой функции ф мы можем по гёделеву номеру произвольного разрешимого множества А найти гёделев номер его дополнения, что противоречит теореме 15.1. Это доказывает, что на самом деле вычислимой функции ф не существует. Теорема 15.4 доказана.
Очевидно, что если мы знаем характеристический индекс разрешимого множества, то мы владеем и разрешающим алгоритмом для этого множества. Теорема 15.4 показывает, что по гёделеву номеру разрешимого множества в принципе невозможно найти разрешающий алгоритм для этого множества, так что в некотором смысле характеристические индексы разрешимых множеств обладают большей ’’информативностью” по сравнению с их гёделевыми номерами.
Каждое конечное множество, являясь разрешимым, имеет гёделев номер и характеристический индекс. Однако конечные множества натуральных чисел допускают еще и нумерацию третьего вида. А именно, если А = {a?i, Х2, . . ., хп}, где Xi < Х2 < . . . < хп, то число 2Г1 + 2Г2 + . . . + 2^" называется каноническим индексом множества А. Каноническим индексом пустого множества считается число 0. Через /),. будем обозначать конечное множество, каноническим индексом которого является число х. Очевидно, что всякое конечное множество имеет единственный канонический индекс, и каждое натуральное число есть канонический индекс некоторого конечного множества. Чтобы в явном виде найти все элементы множества D$, нужно рассмотреть двоичную запись числа х и, если в этой записи цифра 1 стоит на ф + 1)-м месте справа, то г G Вж. Например, число 13 имеет двоичную запись 1101. Следовательно, Вуз = {0,2,3}. Очевидно, что по каноническому индексу конечного множества может быть алгоритмически найден характеристический индекс этого множества. Сейчас мы увидим, что алгоритмический переход от характеристических индексов конечных множеств к их каноническим индексам невозможен. Сначала отметим следующий очевидный факт: существует тотальная одноместная вычислимая функция / : N —> N такая, что f(x) есть число элементов в множестве /),.. каково бы ни было х. Действительно, по числу х мы можем восстановить множество Вж, а затем подсчитать число элементов в нем. С другой стороны, имеет место следующая теорема.
Теорема 15.5. Не существует одноместной частичной вычислимой функции ф такой, что для всякого х, если рж — характеристическая функция некоторого конечного множества А, то значение ф(х) определено и равно числу элементов в множестве А.
Доказательство. Допустим, что такая функция ф существует. Двуместную функцию f зададим следующим образом:
/(ж, у) = </(ж, у) = <1,01,0если работа программы Рг на исходном данном х завершается ровно за у шагов; в противном случае.
/(ж, у) = <
/(ж, у) = <
1,
0
1,
0
Очевидно, что функция / вычислима. По теореме о параметризации существует такая одноместная тотальная вычислимая функция д, что
/(ж, у) ~ р-д^фф)
для любых х, у. Из этого условного равенства и определения функции / следует, что рд^ является харак- теристичекой функцией одноэлементного множества, если х £ К, и пустого множества, если х ^ К. Таким образом, для любого х
^(уИ) =^(уИ) =1, если х Е К;
^(уИ) =
^(уИ) =
0, если х ^ К.
Это противоречит неразрешимости множества К. Значит, на самом деле функция ф не существует. Теорема 15.5 доказана.
Таким образом, по каноническому индексу конечного множества А мы можем найти мощность множества А, а по его характеристическому индексу — нет. Значит, алгоритмический переход от характеристических индексов конечных множеств к их каноническим индексам невозможен, и канонические индексы конечных множеств обладают большей ’’информативностью” по сравнению с их характеристическими индексами.
Рекурсивно неотделимые перечислимые множества
Пусть X — некоторый ансамбль конструктивных объектов. Говорят, что множества А, В С X рекурсивно отделимы, если существует такое разрешимое множество С С X, что А С С, В С (X \ С).
Теорема 16.1. Существует пара рекурсивно неотделимых непересекающихся перечислимых множеств А, В CN.
Доказательство. Пусть
А = {т^Дт) = 0}, В = {т^Дт) = 1}.
Очевидно, что множества Л и В оба перечислимы и не пересекаются. Допустим, что они рекурсивно отделимы. Пусть С С N — такое разрешимое множество, что А С С, В С (N \ С). Характеристическая функция множества С вычисляется некоторой программой Рт. Допустим, что т Е С. Тогда ym(m) = 1, и т Е В, что противоречит включению В С (N \ С). Значит, т ^ С. Тогда ym(m) = 0, и т Е А, что противоречит включению А С С. Таким образом, множество С с указанными свойствами существовать не может. Теорема 16.1 доказана.
Задачи.
Доказать, что образ /(Л) перечислимого множества А относительно частичной вычислимой функции / перечислим.
Доказать, что полный прообраз /-1(Л) перечислимого множества А относительно частичной вычислимой функции / перечислим.
Пусть А, В — перечислимые множества. Доказать, что существуют перечислимые множества Ai, Bi такие, что
Ai С A, Bi С В, Ai П Bi = 0, Ai U Bi = A U В.
Доказать, что следующие множества неразрешимы:
Ai = {х^рк — константа};
Л2 = {ж ДДа) = 6}, где а,Ь — фиксированные числа;
-4з = {(ж, У)\у е ПотфрУ)У
М = {(ж, уфу е ВапфрУфу
Л5 = {х\рж = ру].
Теорема Райса - Шапиро
Семейство вычислимых функций Т С С называется вполне разрешимым, если его индексное множество разрешимо. Доказанная в разделе 13 теорема Райса утверждает, что никакое нетривиальное семейство Т не является вполне разрешимым. Семейство вычислимых функций Т С С называется вполне перечислимым, если его индексное множество перечислимо. Существуют нетривиальные вполне перечислимые семейства вычислимых функций. Таково, например, семейство всех вычислимых функций, принимающих значение 0 в точке 0. Необходимое условие вполне перечислимости семейства вычислимых функций дает теорема Райса - Шапиро.
Конечной функцией называется функция с конечной областью определения. Запись 9 С ф будет означать, что функция ф является продолжением функции 9.
Теорема 17.1 (теорема Райса — Шапиро). Пусть Т — вполне перечислимое семейство одноместных вычислимых числовых функций. Тогда
Т = {/ Е С\ существует конечная функция 9 Е Т такая, что 9 С фф.
Доказательство. Пусть Т7 — вполне перечислимое семейство, т. е. индексное множество 1^ семейства Т7 перечислимо. Семейство
{/ Е С\ существует конечная функция 9 Е Т такая, что 9 С фф,
участвующее в формулировке теоремы, обозначим через Д. Теорему доказываем от противного. Допустим сначала, что неверно включение J С Л. Тогда существует функция / £ У такая, что / не является продолжением никакой конечной функции 9 из У. Пусть Р — программа для МНР, вычисляющая полуха- рактеристическую функцию множества К. Двуместную функцию д определим следующим образом:
g(z, t) ~ <g(z, t) ~ <f(t), если вычисление P(z) не завершается за < t шагов; не определено, если вычисление P(z) завершается за < t шагов.
g(z, t) ~ <
g(z, t) ~ <
Очевидно, что функция д вычислима. По теореме о параметризации существует такая одноместная тотальная вычислимая функция s : N —> N, что для любых z,t имеет место условное равенство g^z,t) ~ (pg^^ty Отсюда и из определения функции д следует, что ys(z) С f. Заметим также, что если z £ К, то вычисление Р^ завершается за конечное число шагов, скажем, to. Тогда, как видно из задания функции д, значения g(z,t) для t > to не определены, и функция ys(z) конечна. Следовательно, ys(z) ^ У и s(z) ^ Ту. Если же z ^ К, то g(zД) ~ /(/) при любом t, и ys(z) = f. Следовательно, в этом случае ys(z) £ У и s(z) £ Ту. Таким образом, мы видим, что для любого z
z ^ К ЕЕ s(z) £ 1г,
откуда вытекает, что дополение множества К перечислимо. Полученное противоречие показывает, что допущение неверно, и на самом деле У С Д.
Допустим теперь, что неверно включение А С У. Тогда существует конечная функция 9 Е У такая, что / является продолжением функции 9, но f ^ У. Двуместную функцию д определим следующим образом:
/ Г если t Е Dom(9) или z Е К; q\z,t\ ~ <
(не определено в остальных случаях.
Очевидно, что функция д вычислима. По теореме о параметризации существует такая одноместная тотальная вычислимая функция s : N —> N, что для любых z,t имеет место условное равенство g^zД) ~ ipsp,yty Отсюда и из определения функции д следует, что если z £ К, то ys(z) = f, следовательно, ys(z) ^ У и s(z) ^ Ту. Если же z ^ К, то из того факта, что f является продолжением функции 9, следует, что ^(z) = 9, следовательно, ys(z) Е У и s(z) £ 1у. Таким образом, мы видим, что для любого z
z ^ К ЕЕ s(z) Е 1г,
откуда вытекает, что дополнение множества К перечислимо. Полученное противоречие показывает, что допущение неверно, и на самом деле А С У. Таким образом, мы доказали оба включения У С А и А С У. Следовательно, У = А, и теорема 17.1 доказана.
Теорема Райса - Шапиро позволяет легко доказывать неперечислимость некоторых множеств. Так, ранее мы доказали, что множество гёделевых номеров одноместных тотальных вычислимых числовых функций неперечислимо. Теперь этот же результат может быть получен с помощью теоремы Райса - Шапиро. Действительно, рассматриваемое множество — это индексное множество семейства У всех одноместных тотальных вычислимых числовых функций. Это семейство не содержит ни одной конечной функции, так что никакая функция из У не является продолжением конечной функции из У, и по теореме Райса - Шапиро У не будет вполне перечислимым.
Теорема Райса - Шапиро может быть переформулирована и доказана и для семейств перечислимых множеств. Семейство К. перечислимых подмножеств натурального ряда будем называть вполне перечислимым, если перечислимо его индексное множество. Класс конечных множеств V называется канонически перечислимым, если перечислимо множество канонических индексов всех множеств из V.
Теорема 17.2. Семейство К. перечислимых подмножеств N вполне перечислимо тогда и только тогда, когда существует канонически перечислимое семейство конечных множеств D такое, что
(4)(4)(УЛ)[Л Е К, ЕЕ (Л перечислимо и (BD)(D EDW С Л))].
(4)
(4)
Доказательство. Пусть К. — вполне перечислимое семейство перечислимых множеств. Пусть V — семейство всех конечных множеств из К.. Докажем, что множество канонических индексов {T|2?r Е Р{ всех множеств из V перечислимо. А именно, убедимся, что оно полуразрешимо. Пусть дано натуральное число х. Как было отмечено в разделе 15, по числу х можно эффективно, т. е. с помощью алгоритма, найти характеристический индекс множества D$, а затем — с помощью теорем, доказанных в разделе 15, — гёделев номер этого множества, т. е. такое число ф^хУ что D$ = ИД^у Применим к этому числу алгоритм, вычисляющий полухарактеристическую функцию индексного множества семейства К.. Очевидно, что результат
будет получен в том и только в том случае, когда множество ИД,^) принадлежит семейству /С, т. е. множество D$, принадлежит семейству Р. Таким образом, множество канонических индексов всех множеств из D перечислимо. Итак, D — канонически перечислимое семейство.
Рассмотрим теперь семейство вычислимых функций
UEC\Dom^ е/С}.
Очевидно, что индексные множества семейств К. и У совпадают. Так как семейство К. вполне перечислимо, то таково же и семейство Т. По теореме 17.1 функция / принадлежит семейству Т тогда и только тогда, когда она является продолжением некоторой конечной функции из Т. В силу определения семейства Т это означает, что произвольное перечислимое множество принадлежит семейству К. тогда и только тогда, когда оно имеет конечное подмножество из /С, а значит, и из D. Таким образом, семейство D является канонически перечислимым и удовлетворяет условию (4).
Докажем теперь, что если для данного семейства перечислимых множеств К. существует канонически перечислимое семейство конечных множеств D такое, что выполняется условие (4), то семейство К. вполне перечислимо. Если семейство D пусто, то, очевидно, семейство К. также пусто, следовательно, вполне перечислимо. Если же семейство D не пусто, то множество канонических индексов всех множеств из D перечисляется некоторой вычислимой функцией. Опишем алгоритм, вычисляющий полухарактеристическую функцию индексного множества семейства /С. Пусть дано натуральное число х. Будем перечислять элемент за элементом множество канонических индексов всех множеств из D. Получая очередной элемент у этого множества, выписываем элементы множества Dy и запускаем алгоритм проверки этих элементов на принадлежность их множеству ИД, т. е. на каждом из них начинаем вычислять значение функции у^. Пока процесс вычисления идет, мы находим следующий элемент у из множества канонических индексов всех множеств из Р и запускаем алгоритм проверки его элементов на принадлежность их множеству ИД, и т. д. Если окажется, что все элементы какого-то из этих множеств Dy принадлежат множеству ИД, делаем вывод, что ИД принадлежит семейству К., а х принадлежит индексному множеству семейства /С. Следовательно, индексное множество семейства К. перечислимо, а само это семейство вполне перечислимо. Теорема 17.2 доказана.
Задачи.
Вывести теорему Райса из теоремы Райса - Шапиро.
Доказать, что множество гёделевых номеров всех нетотальных вычислимых функций неперечислимо.
Доказать, что множество гёделевых номеров всех вычислимых неинъективных функций перечислимо.
Выяснить, какие из следующих множеств разрешимы, какие перечислимы, какие имеют перечислимое дополнение:
{т|т G ИД};
{т|т есть полный квадрат};
{х^к есть инъективная функция};
{ж| в десятичном разложении числа тг существуют х идущих друг за другом семерок};
{^l^m^He определено} (т фиксировано).
Многозначная сводимость
Доказывая неразрешимость некоторых множеств, мы часто пользовались следующим приемом: мы показывали, что если бы существовал разрешающий алгоритм для данного множества, то мы имели бы разрешающий алгоритм и для некоторого заведомо неразрешимого множества, например, К. В общем случае этот прием называется сведением одной алгоритмической проблемы к другой. Понятию сведёния можно придать точный смысл многими различными способами. Мы рассмотрим один из них — многозначную сводимость.
Будем говорить, что множество А С N многозначно сводится (или т-сводится) к множеству В С N (Д <т В), если существует тотальная вычислимая функция / : N —> N такая, что
(\Д)[т ЕЙ» /(ж) G В].
В этом случае будем говорить, что А сводимо к В посредством функции /, а функцию / будем называть сводящей А к В.
Примеры.
Пусть В есть множество всех гёделевых номеров функции, тождественно равной 0. Тогда К <т В. Чтобы доказать это, рассмотрим двуместную функцию д, определяемую так:
д(х,у) =д(х,у) =0, если х G К;
д(х,у) =
д(х,у) =
не определено, если х ^ К.
Очевидно, что функция д вычислима. По теореме о параметризации существует одноместная тотальная вычислимая функция / такая, что для любых х, у выполняется условное равенство д^х, у) ~ VfA'i ^V Отсюда и из определения функции д немедленно следует, что если х £ К, то функция Pf^ тождественно равна 0, т. е. f(x) Е В, а если х ^ К, то функция Pf^ нигде не определена, и f(x) ^ В. Таким образом, (Vt)[t G К ЕР f(x) G В], т. е. К <т В.
Анализ доказательства теоремы Райса показывает, что множество К m-сводится к индексному множеству любого нетривиального семейства вычислимых функций, не содержащего нигде не определенную функцию.
Пусть А — множество всех гёделевых номеров тотальных одноместных вычислимых числовых функций, а В — множество всех гёделевых номеров функции, тождественно равной 0. Тогда А <т В. Для доказательства рассмотрим двуместную функцию д(х,у) ~ 0 • p^^yY Очевидно, что эта функция вычислима. По теореме о параметризации существует одноместная тотальная вычислимая функция f такая, что для любых х, у выполняется условное равенство д(х,у) ~ pj^^yY Отсюда и из определения функции д немедленно следует, что если х Е А, то функция Pf^ тождественно равна 0, т. е. f(x) Е В, а если х ^ А, то функция ^(ж) не всюду определена, и f(x) ^ В. Таким образом, (Vt)[t Е А ЕР f(x) 6 В], т. е. А <т В.
Теорема 18.1. 1. Отношение <т рефлексивно и транзитивно.
А <т В тогда и только тогда, когда А <т В.
Если множество В разрешимо, и А <т В, то множество А разрешимо.
Если множество А разрешимо, В ф 0, В ф N, то А <т В.
Если множество В перечислимо, и А <т В, то множество А перечислимо.
А <т N G^ А = N;
А <т 0 о А = 0;
N <т А ^ А 0;
0 <т А ЕР А N.
Доказательство. 1. Очевидно, что А сводится к А посредством тождественной функции, так что А <т А, и отношение <т рефлексивно. Очевидно также, что если А сводится к В посредством функции f, а В сводится к С посредством функции д, то А сводится к С посредством композиции этих функций, т. е. такой функции h, что (\/т)/г(т) = g(f(x)Y
Очевидно, что если А сводится к В посредством функции f, то А сводится к В посредством той же функции.
Очевидно, что если А сводится к В посредством функции f, то (Уж)ха(ж) = Хв(/(т)), так что если множество В разрешимо, т. е. функция %в вычислима, то функция %А также вычислима, т. е. множество А разрешимо.
Если В ^ 0, В 7^ N, возьмем b Е В, с ^ В. Если А разрешимо, то вычислима функция
f^ = (f^ = (если х Е А;
f^ = (
f^ = (
если х ^ А.
Очевидно, что функция f вычислима, и А сводится к В посредством f.
Очевидно, что если А сводится к В посредством функции f, то (^x^Ya^ = YB^f^YY так что если множество В перечислимо, т. е. функция Yb вычислима, то функция Ya также вычислима, т. е. множество А перечислимо.
Согласно пункту 1, N <т N. С другой стороны, если А сводится к N посредством функции f, то х Е А УД f(x) Е N. Правая часть этой эквивалентности выполняется для любого х, значит, левая тоже, и А = N.__
A<m0^A<mN^A = N^A = 0.
Пусть N сводится к А посредством функции /. Тогда А = Ran(fY так что А ^ 0. С другой стороны, если А ^ 0, возьмем произвольное с Е А. Тогда N сводится к А посредством функции, тождественно равной с.
0<mA^N<mA^A^0^A^N.
Теорема 18.1 доказана.
Следующая теорема показывает, что множество К в некотором смысле играет ключевую роль среди перечислимых множеств.
Теорема 18.2. Множество А С N перечислимо тогда и только тогда, когда А <т К.
Доказательство. Тот факт, что если А <т К, то А перечислимо, вытекает из пункта 5 теоремы 18.1 и того факта, что множество К перечислимо. Обратно, пусть А С N — произвольное перечислимое множество. Двуместную числовую функцию g определим следующим образом:
дУАу) =дУАу) =если х G А;
дУАу) =
дУАу) =
не определено, если х ^ А.
Очевидно, что функция д вычислима. По теореме о параметризации существует одноместная тотальная вычислимая функция / такая, что для любых х, у выполняется условное равенство д^х, у) ~ Pf^ ^V Отсюда и из определения функции д немедленно следует, что если х £ А, то функция Pf^ всюду определена, в частности, определено значение pj^(f(x)y т. е. f(x) £ К, а если х ^ А, то функция Pf^ нигде не определена, и f(x) ^ К. Таким образом, (\Л)[т £ А УД f(x) £ К], т. е. А <т К. Теорема 18.2 доказана.
Задачи.
Пусть с — фиксированное число, В = {т|с £ ИЛ}- Доказать, что К <т В.
Пусть А — множество всех гёделевых номеров тотальных одноместных вычислимых числовых функций. Доказать, что А не m-сводится к К.
Доказать, что если А — перечислимое множество, не являющееся разрешимым, то А не m-сводится к Л, и Л не m-сводится к А.
Продуктивные множества
Как мы знаем, дополнение К множества К неперечислимо. Этот факт может быть выражен в более сильной форме: существует алгоритм, который позволяет по гёделеву номеру х любого перечислимого подмножества ИЛ множества К найти натуральное число из К, не принадлежащее ИД. А именно, в качестве такого числа можно взять х. Действительно, пусть ИД С К. Предположим, что х £ ИД. Тогда х £ К, что невозможно. Значит, х ^ ИД, следовательно, х £ К и х £ (К \ ИД). Это свойство множества К приводит к следующему общему определению: множество Л С N называется продуктивным, если существует одноместная вычислимая числовая функция ^ такая, что
(Дс)[ИД с Л^ (!^(т)М(ж) еЛ\^)].
В этом случае функция ^ называется продуктивной функцией для множества А. Непосредственно из определения вытекает, что продуктивное множество неперечислимо. Как показано выше, множество К является продуктивным, причем тождественная функция ф^х) = х является продуктивной функцией для К. Много других примеров продуктивных множеств можно получить с помощью следующей теоремы.
Теорема 19.1. Пусть множество А продуктивно, и А <т В. Тогда множество В продуктивно.
Доказательство. Пусть А сводимо к В посредством функции J. Рассмотрим двуместную функцию h(x,y) ~ Рж^Ф^У Очевидно, что эта функция вычислима. По теореме о параметризации существует одноместная тотальная вычислимая функция к такая, что для любых х, у выполняется условное равенство h(x,y) ~ Рк^УтУ Отсюда и из определения функции h следует, что значение рц^УТ) определено тогда и только тогда, когда определено значение РзУФфуУ). Это означает, что у £ ИЛ (г) УД /(у) £ ИЛ, т. е. Wk^) = /“^ИЛ). Допустим теперь, что ИЛ С В. Тогда из определения m-сводимости следует, что
Wk^ = r4w^ с А.
Пусть g — продуктивная функция для А. Тогда д(ЦхУ) 6 (А \ ИД^}), откуда следует, что
ЖН4У е (В\жд.
Следовательно, функция ^(т) = f^flU^x))) является продуктивной для множества В. Теорема 19.1 доказана. Рассмотрим некоторые применения теоремы 19.1.
Пример 1. В разделе 18 было доказано, что множество К m-сводимо к множеству гёделевых номеров функции 0, тождественно равной нулю. Следовательно, множество К m-сводимо к множеству {х\рж ф 0}, которое, таким образом, оказывается продуктивным.
Пример 2. Как было замечено в разделе 18, множество К m-сводимо к индексному множеству 1^ любого нетривиального семейства вычислимых функций У, не содержащего нигде не определенную функцию. Отсюда следует, что если нетривиальное семейство вычислимых функций У содержит нигде не определенную функцию, то К <т 1^, следовательно, в этом случае множество 1^ является продуктивным.
Теорема 19.2. Любое продуктивное множество содержит бесконечное перечислимое подмножество.
Доказательство. Пусть А — продуктивное множество, g — его продуктивная функция. Последовательность / : N —> N определим следующим образом. Пусть ео — гёделев номер программы для МНР, состоящей из единственной команды
J(l,l,l).
Очевидно, что в этом случае Жео = 0, следовательно, Жео С А, и значение уо = у(ео) определено. В качестве /(0) возьмем уо. При этом, очевидно, уо £ А. Допустим теперь, что мы уже вычислили значения /(г) = у; для г = 0, . . ., п, причем ^уо, . . ., уп} С А. Пусть en+i — гёделев номер программы для МНР, завершающей работу только на исходных данных уо, . . .,уп. Очевидно, что в этом случае Жеп+1 = ^уо, . . . ,упф следовательно, Жеп+1 С А, и значение yn+i = <7(en+i) определено. В качестве f(n + 1) возьмем ynpi. При этом, очевидно, Уп+i G А и Уп+1 ^ {г/о, • • • ,У«У Таким образом, / — вычислимая последовательность, множество ее значений Ran(f) бесконечно, перечислимо и содержится в А. Теорема 19.2 доказана.
Задачи.
Доказать, что следующие множества продуктивны:
{т|с ^ Жг} (с — фиксированное число);
{т|с ^ Ran^p^)^ (с — фиксированное число);
{т|Жг конечно};
{х^рц, не сюръективна};
{х^рц, инъективна};
{х^рц, тотальна};
{х^рц, является многочленом};
{х^рц, не является многочленом}.
Доказать, если А перечислимо, а множество АЛВ продуктивно, то В также продуктивно.
Доказать, что любое продуктивное множество содержит бесконечное разрешимое подмножество.
Креативные множества
Множество А С N называется креативным (или творческим), если оно перечислимо, а его дополнение А продуктивно. Самым простым примером креативного множества является множество К. Другим примером может служить множество
А = {т|^>г(т) = 0}.
Очевидно, что это множество перечислимо. Построим продуктивную функцию для его дополнения. Для этого рассмотрим двуместную функцию /, определяемую следующим образом:
О, если значение рДу) определено;не определено в противном случае.
Очевидно, что эта функция вычислима. По теореме о параметризации существует одноместная тотальная вычислимая функция g такая, что для любых х, у выполняется условное равенство f(x, у) ~ рд^(у). Отсюда и из определения функции / следует, что значение рд^(д(х)) определено (и равно 0) тогда и только тогда,
когда определено значение р^д^х)). Таким образом, д(х) £ А <Р д(х) £ Жг, так что если Жг С А, то должно выполняться условие д(х) G (А \ Wx), т. е. д — продуктивная функция для А. Много других примеров креативных множеств можно получить с помощью следующей теоремы.
Теорема 20.1. Пусть У — нетривиальное семейство одноместных числовых вычислимых функций, А — его индексное множество. Если множество А перечислимо, то оно креативно.
Доказательство. Если нигде не определенная функция не принадлежит семейству У. то, как отмечалось выше, из доказательства теоремы Райса следует, что множество А продуктивно, следовательно, не может быть перечислимым. Значит, нигде не определенная функция принадлежит дополнению семейства У, а тогда дополнение множества А продуктивно. Следовательно, А креативно. Теорема 20.1 доказана.
Непосредственным применением этой теоремы доказывается, например, что множество {т|с ^ ИД} и {т|с ^ Ran(px^ (с — фиксированное число) является креативным.
Задачи.
Доказать, что следующие множества креативны:
{т|Ж,^0};
{т|т G Кап^р^У,
{х\рх не инъективна};
{т^Дт) = /(ж)}, где / — произвольная тотальная вычислимая функция.
Доказать, что если множество А креативно, а множество В перечислимо, причем А С В = 0, то множество ЛиВ креативно.
Простые множества
Множество Л С N называется простым, если выполнены следующие условия:
А перечислимо;
А бесконечно;
е Л не содержит бесконечного перечислимого подмножества.
Теорема 21.1. Простое множество не является ни разрешимым, ни креативным.
Доказательство. Пусть А — простое множество. В силу определения простого множества, его дополнение не перечислимо. Отсюда по теореме Поста получаем, что А не разрешимо. Из теоремы 19.2 и определения простого множества следует, что множество А не является простым, следовательно, А не является креативным. Теорема 21.1 доказана.
Теорема 21.2. Существует простое множество.
Доказательство. Одноместную числовую функцию f определим следующим алгоритмом ее вычисления. Пусть дано натуральное число х. Чтобы найти f(x), будем последовательно вычислять значения
^(0),^(1),...
(при этом вычисление рх (n + 1) начинается только после того, как вычисление рх (п) завершилось); вычисления прекращаются, если найдено такое число п, что рх(п) > 2п; в этом случае полагаем f(x) = px(nY Таким образом, f — вычислимая функция. Тогда множество ее значений перечислимо. Докажем, что множество А = Ran(f^) является простым. Пусть В — произвольное бесконечное перечислимое множество. Тогда В является множеством значений некоторой вычислимой последовательности рь- Из определения функции / видно, что в этом случае значение /(6) определено и /(6) 6 В. Значит, В не содержится в дополнении множества А. Чтобы убедиться, что множество А бесконечно, заметим, что если значение f(x) определено, то f(x) > 2т. Таким образом, для любого п в множестве {0, 1,2,..., 2п} содержатся не менее п элементов из А. Следовательно, множество А бесконечно. Теорема 21.2 доказана.
m-полные перечислимые множества
Множество А С N называется т-полным, если оно перечислимо, и любое другое перечислимое множество m-сводимо к Л. В разделе 18 было показано, что множество К является m-полным. Отсюда и из транзитивности отношения <т следует, что перечислимое множество А является m-полным тогда и только тогда, когда К <т А.
Множество К перечислимо, но не разрешимо. Возникает естественный вопрос: всякое ли неразрешимое перечислимое множество является m-полным? Сейчас мы получим ответ на этот вопрос.
Теорема 22.1. Любое т-полное множество креативно.
Доказательство. Если множество А m-полно, то К <т А. Следовательно, К <т А. Так как К продуктивно, то по теореме 19.1 множество А также продуктивно, а тогда А креативно. Теорема 22.1 доказана.
Имеет место и обратное утверждение: всякое креативное множество является m-полным. Однако доказательство этого утверждения требует более глубокого изучения теории алгоритмов и не входит в наши планы.
Теорема 22.2. Простые множества не являются т-полными.
Доказательство. По теореме 22.1 любое m-полное множество креативно, в то же время теорема 21.1 утверждает, что простые множества не являются креативными. Теорема 22.2 доказана.
Таким образом, простые множества перечислимы, не разрешимы, но не являются т-полными.
Язык формальной арифметики
Сейчас мы рассмотрим некоторые применения теории алгоритмов в математической логике. Как известно, математическая логика математическими методами изучает математические рассуждения. Всякое рассуждение есть в некотором смысле логически правильная последовательность утверждений. Чтобы сделать математические утверждения точными математическими объектами, для их записи в математической логике разработаны искусственные, формализованные языки. Мы рассмотрим один из таких языков — язык формальной арифметики, предназначенный для записи утверждений о натуральных числах. Как и всякий формализованный язык, язык формальной арифметики использует фиксированный алфавит. Алфавит языка формальной арифметики содержит следующие символы: константы 0 и 1, символы для операций сложения + и умножения •, символ для отношения равенства =, а также символы для логических операций -л (отрицание), & (конъюнкция), V (дизъюнкция), D (импликация) и кванторов всеобщности V и существования Я. Кроме того, в языке формальной арифметики имеются счетное множество переменных К = {го, г>1, «2, • • •} и скобки (, ).
Среди всех слов в описанном алфавите различаются два типа осмысленных выражений — термы и формулы. Терм — это формальный аналог числовой формы. Термы строятся по следующим правилам:
константы 0 и 1 являются термами;
всякая переменная является термом;
если Ч и /2 — термы, то выражения (Ч + ^) и (Ч • /2) являются термами.
Например, термами являются выражения 0, 1, (1+1), ((!+!) + !) нт. д. Очевидно, что эти термы являются записями чисел 0, 1, 2, 3 и т. д. В дальнейшем мы будем через п обозначать терм, являющийся записью натурального числа п. Например, 7 есть ((((((1+1) + 1) + 1) + 1) + 1) + 1).
Формула является формальным аналогом высказывания или высказывательной формы. Формулы строятся по следующим правилам:
если П и /2 — термы, то выражение Ч = /2 является формулой;
если Ф — формула, то выражение -,Ф является формулой;
если Ф и Ф — формулы, то выражения (Ф&Ф), (Ф V Ф), (Ф D Ф) являются формулами;
если Ф — формула, х — переменная, то выражения УтФ и ЭтФ являются формулами.
Например, формулой является выражение 3i’i(i’i •(! + !)) = uq. Очевидно, что эта формула является записью высказывательной формы ”то — четное число” . Формула Зщ (щ -2) = 5 выражает ложное высказывание, а формула Зщ(щ • 2) = 4 выражает истинное высказывание.
Выражает ли данная формула высказывание или высказывательную форму, зависит от присутствия в ней свободных вхождений переменных. Свободные и связанные вхождения переменных в формулу различаются следующим образом. В формуле вида УтФ или ЭтФ ее часть V® или Эт называется кванторной приставкой, а Ф — ее областью действия. Вхождение переменной х называется связанным, если оно находится в кванторной приставке V® или Зх или в ее области действия. Вхождение переменной называется свободным, если оно не является связанным.
Формула, не содержащая свободных вхождений переменных, называется замкнутой формулой или высказыванием. Очевидно, что всякое высказывание оказывается истинным или ложным при естественном понимании всех входящих в него символов. Обозначим через Т множество всех истинных высказываний, а через У — множество всех ложных высказываний.
Если формула Ф(т1, . . ., хп) не содержит свободных вхождений переменных, отличных от хх, . . ., хп, то она превращается в высказывание Ф(&1, . . . ,кп), если вместо этих свободных вхождений подставить соответственно термы кх, . . ., кп, изображающие натуральные числа кх,..., кп. Поэтому такая формула может рассматриваться как высказывательная форма. Например, отношение х < у выражается формулой
Зго^о = 0 & (ж + го) = у).
Поэтому в дальнейшем вместо такой формулы мы иногда будем писать просто х < у.
Арифметические множества и функции
Пусть п > 1 — натуральное число. Множество А С Nn называется арифметическим, если существует арифметическая формула ФуДщ, • • •, Гп) со свободными переменными только из списка щ,. . ., vn такая, что для любых натуральных чисел кх, . . ., кп выполняется следующее условие:
(кх,- ..,ЦеА^ Ф(^!,.. .,кп) е Т.
В этом случае будем говорить, что формула Фа(^1, • • •, ^п) определяет множество А.
Теорема 24.1. Если множества А, В С Nn являются арифметическими, то множества Nn \ A, A U В, АС\ В также являются арифметическими.
Доказательство. Пусть множества Л и В определяются соответственно формулами Фа(^1, • • •, ^п) и Фв^!, . . ., ипф Тогда, очевидно, множество Nn \ А определяется формулой -|Фл(г1, . . ., ипф множество ЛиВ определяется формулой Фа (^1, • • •, ^п) V Фв(г1,. . ., ип), а множество ЛАВ определяется формулой Фа(щ, . . ., ип) к Фв^г, • • •, ^п)- Теорема 24.1 доказана.
Частичная функция / из множества Nn в множество N называется арифметической, если ее график Г у является арифметическим множеством. Формулу, определяющую график арифметической функции f, будем обозначать ФДщ, . . ., vn, vn-i-x)-
Теорема 24.2. Всякая вычислимая числовая функция является арифметической.
Доказательство. В силу тезиса Чёрча всякая вычислимая числовая функция является частично-рекурсивной. Поэтому достаточно доказать, что всякая частично-рекурсивная функция является арифметической. Сначала докажем арифметичность базисных функций. Очевидно, что функция s(t) = х + 1 определяется формулой «2 = (fl + 1); функция о(х) = 0 определяется формулой «2 = 0; функция 1^(хх, . . ., хп) = хт определяется формулой «n+i = ит.
Докажем теперь, что если арифметичны fc-местная функция f и «-местные функцие ух, . . ., ук, то п- местная функция h, получающаяся из них подстановкой, также арифметична. Пусть
Ф/Л1, . . • , Vk, f& + l), ФдЛ^Ь • • - Ап Ап-nW = 1, • • -
суть формулы, определяющие соответствующие функции. Тогда, очевидно, функция h определяется следующей формулой:
3«i .. .ЯнДФдДщ,..., vn, и-ф) & ... &Ф№ (щ,..., г„, ик) кФ^их,..., ик, r„+i)).
Докажем, что если «-местная (n > 1) частичная функция д получается с помощью минимизации из (« + 1)-местной частичной арифметической функции /, то функция д также арифметична. Пусть формула Фд(щ, . ..,ип, «„+1, уп+з) определяет функцию д. Тогда, очевидно, функция / определяется следующей формулой:
Vy(y < г„+1 D ^«(ФДщ,..., -с», щ w) & -iw = 0)) & Фд(щ,..., vn, г„+1,0).
Случай, когда (« + 1)-местная (n > 1) частичная функция h получается с помощью операции рекурсии из «-местной арифметической функции / и (« + 2)-местной арифметической функции д, требует некоторой изобретательности. Пусть х, у, z — натуральные числа. Говорят, что число z сравнимо с числом у по модулю х и пишут z = y(moda?), если числа z и у дают одинаковые остатки при делении на х или, что то же самое, если их разность z — у делится на х. Отметим следующий известный факт из алгебры: если числа w и х взаимно просты, то существует такое число z, что wz = l(moda?).
Лемма 24Л (китайская теорема об остатках). Каковы бы ни были натуральные числа ур . . . ,ук и натуральные попарно взаимно простые числа хр . . ., xk, существует натуральное число z такое, что
z = i/i(modЖ1),. . ., z = уДтодхД.
Доказательство. Пусть х = Ху . . ,хк. Тогда х = wiXi = . . .wkxk для подходящих чисел гщ,. . ., wk. Для любого г = 1,...Д числа гщ и х; взаимно просты, следовательно, существует такое число zp что w^z-i = l(modTj). Положим теперь z = upziyi + . . . + wkzkyk. Тогда z = t/i(modT,) для любого г = 1, . . ., к. Лемма 24.1 доказана.
Пусть гт(т,у) обозначает остаток от деления числа у на число х. Рассмотрим следующую функцию: Р)х, у, z) = rm(l + (z + 1) • у, х) (обычно ее называют P-функцией Гёделя).
Лемма 24.2. Для любой конечной последовательности натуральных чисел ко, кр . . ., кп существуют такие натуральные числа Ь и с, что для любого г = 0, 1, . . ., п имеет место равенство P)b, с, i) = кр
Доказательство. Пусть ] = max(n До Д1, • • • Дп) и с = jl. Рассмотрим числа щ = 1 + (г + 1) • с (г = 0, 1, ..., п). Они попарно взаимно просты. Действительно, если бы числа щ и ит, где 1 < I < т < п, имели простой общий делитель р, то р было бы делителем их разности ит — щ = (m — I) • с, а значит, и делителем хотя бы одного из чисел m-hc. Но так как т — 1 < j, то в любом случае с делится на р. Однако очевидно, что тогда ни up ни ит не могут делится на р. Полученное противоречие показывает, что на самом деле числа щ и ит взаимно просты. Согласно китайской теореме об остатках (лемма 24.1), существует число b такое, что для любого г = 0, 1, . . ., п имеет место равенство b = ^ДтобнД, т. е.число b даеттакойже
остаток при делении на up как и число кр Заметим, что для любого г = 0, 1, . . .,п выполняютсяусловия
kj < j < j! = с < 1 + (г + 1) • с = up т. е. ki < up Это означает, что rm(u,-, к;) = кр Теперь имеем:
Р)Ь, с, г) = rm(l + (i + 1) • с, b) = rm(u,-, b) = rm(u,-, кр = кр
что и требовалось доказать. Лемма 24.2 доказана.
Заметим, что функция Р является арифметической: она определима формулой
Зу5У1 = (((1 + (Дз + 1) • уз)) • «ь) + уД & У4 < ((1 + (Дз + 1) • уз))),
которая, естественно, обозначается Фд(ут, «2, Уз, У4Д
Вернемся к доказательству теоремы 24.2. Пусть (« + 1)-местная (« > 1) частичная функция h получается с помощью рекурсии из «-местной арифметической функции / и (« + 2)-местной арифметической функции д. Пусть Фу (щ, . . ., ип, уп+1, Уп+з), Фд(У1 , • • •, Уп+з, Уп+з) — формулы, определяющие соответствующие функции. Тогда, очевидно, функция h определяется следующей формулой:
ЗиЗ-иДЗгДФ/Ди, v, 0, up & Ф/(у1, ..., у„, w))) & Фд(«, у, у„+1, у„+з) &
& Vw(w < D Зг/ЗДФд(«, гр w, у) &
& Фд(и, -и, (ш + 1), z) & Фд(У1, . . ., у„, W, у, г)))).
Отдельно рассмотрим случай, когда одноместная функция h получается рекурсией из числа а и двуместной функции д. Пусть Ф9(у1,уз,уз) — формула, определяющая функцию д. Тогда функция h определяется следующей формулой:
3«Зг(Фд(«,г,0,а)&Фд(«,г,Т1,Г2) & Vw(w < щ D Зг/Зг(Фд(«, гр ир у) &
& Фд (и, у, (w + 1), z) к Фд(гу, у, г)))).
Итак, мы доказали, что все базисные функции являются арифметическими, а с помощью операций подстановки, рекурсии и минимизации из арифметических функций получаются только арифметические функции. Следовательно, всякая частично-рекурсивная функция арифметична. Теорема 24.2 доказана.
Теорема 24.3. Всякое перечислимое множество AC N является арифметическим.
Доказательство. Пусть множество А С N перечислимо. Тогда оно является областью определения некоторой вычислимой функции f. По теореме 24.2, функция f арифметична. Пусть ФДщ, гд) — формула, определяющая функцию f. Так как А является областью определения функции f, то, очевидно, формула ЯгдФДщ, гд) определяет множество А. Теорема 24.3 доказана.
Теорема 24.4. Существует неперечислимое арифметическое множество.
Доказательство. Пусть А — какое-нибудь неразрешимое перечислимое множество. По теореме 24.3 оно является арифметическим. По теореме 24.1 его дополнение также арифметично, но оно, очевидно, неперечислимо. Теорема 24.4 доказана.
Задачи.
Доказать, что множество всех простых чисел является арифметическим.
Доказать, что если множества А, В С N арифметичны, то их разность А \ В также арифметична.
Для следующих функций написать определяющие их арифметические формулы:
а)f ' ’ ®сли ж четно>б) /(ж,= жу (здесь0° = 1); в) /(ж)= ж! (здесь 0! = 1);
' Jv '( х + 1, если х нечетно; ) J \vj \\
., . Г1, если х > 0;. , . f0, если х > 0;. , Г х — 1, если х > 0;
г) sg(ж)= 1д) sg(ж)= 1е) р(ж)= 1
''[ 0, если х = 0;''если х = 0;’ ' '[ 0, если х = 0;
хI х — у, если х > у, , ,,,,.,. ,,,. „,
ж) а(х) = j Q если < - з) |ж —у|; и)шах(ж,у); к)шш(т,у); л) х - у; м) -; и) ^х;
°) п) Ш-
Гёделева нумерация арифметических формул
Каждому символу а из алфавита языка формальной арифметики сопоставим натуральное число у (а), называемое гёделевым номером символа а: у(0) = 3, у(1) = 5, у(+) = 7, у^ = 9, у(=) = И, д^) = 13, д№ = 15, y(V) = 17, д(^ = 19, д^) = 21, у(Я) = 23, д(0 = 25, дф = 27, д(щ) = 29 + 2i (i = 0,1, 2,...). Таким образом, различным символам поставлены в соответствие различные нечетные натуральные числа.
Каждому слову w = ао«1 ... ап в алфавите языка формальной арифметики сопоставим натуральное число
y(w) = 2"° •З"1 • . ..•р“",
где рп есть п-е простое число, если считать ро = 2. Число y(w) будем называть гёделевым номером слова w. В частности, каждый терм t имеет некоторый гёделев номер у(Д, и каждая формула Ф имеет некоторый гёделев номер д(Фф Например, д(ио = ^1) = 229 • З11 • 531. Заметим, что в силу единственности разложения натуральных чисел в произведения степеней простых чисел различные выражения получают различные гёделевы номера. Кроме того, гёделевы номера выражений чётны и потому отличны от гёделевых номеров символов. Такая нумерация символов и выражений языка формальной арифметики была впервые введена Гёделем с целью замены высказываний о математических утверждениях на высказывания о натуральных числах.
Рассмотренный здесь способ построения гёделевых номеров не является единственно возможным. Главной отличительной особенностью этой и других гёделевых нумераций является существование алгоритма, позволяющего по любому выражению найти его гёделев номер, и алгоритма, который для любого натурального числа п позволяет определить, является ли п гёделевым номером какого-нибудь выражения и, если является, найти это выражение.
Если А — некоторое множество выражений языка формальной арифметики, ему соответствует множество lx С N, состоящее в точности из гёделевых номеров выражений, входящих в А. Будем называть 1х индексным множеством множества выражений А. Теперь все эпитеты, которыми награждаются числовые множества, могут быть применены к множествам выражений языка формальной арифметики, так что множество выражений А будет называться разрешимым, перечислимым, продуктивным, креативным, арифметическим и т. д., если его индексное множество 1^ является соответственно разрешимым, перечислимым, продуктивным, креативным, арифметическим и т. д.
Теорема Тарского
С чисто математической точки зрения наиболее интересен вопрос о свойствах множества Т всех истинных высказываний. В некотором смысле окончательный ответ на этот вопрос дает следующая теорема.
Теорема 26.1 (теорема Тарского). Множество всех истинных высказываний языка формальной арифметики не является арифметическим.
Доказательство. Допустим, что множество Т всех истинных высказываний языка формальной арифметики арифметично, и ФтДщ) — формула, определяющая множество Lp, т. е. множество гёделевых номеров всех истинных формул. Последнее означает, что каково бы ни было натуральное число п, формула Фт~(п) истинна тогда и только тогда, когда п является гёделевым номером истинной замкнутой формулы.
Рассмотрим следующую двуместную частичную числовую функцию:
, ,, _ ( у(Ф(у)), если х = у(Ф(щ)) для некоторой формулы Ф;
' ’ (не определено в противном случае.
Очевидно, что эта функция вычислима. Она вычисляется следующим алгоритмом: ’’Пусть даны натуральные числа х и у. Определите, является ли х гёделевым номером какой-либо формулы Ф^х). Если это так, то вместо всех свободных вхождений переменной щ в формулу Ф(щ) подставьте терм, изображающий число у. Вычислите гёделев номер полученной формулы. Это и есть значение 8и6(т,у).” Поскольку функция sub вычислима, то в силу теоремы 24.2 она арифметична. Пусть ФзибС^т, ^2, ^з) — формула, определяющая функцию sub. Рассмотрим формулу Зг’о(Фзи{>(г’1, щ, гд) & -,Фт('уо)), которую обозначим Ф(щ). Эта формула имеет свободные вхождения только переменной щ и, очевидно, утверждает, что замкнутая формула, полученная подстановкой терма щ" вместо свободных вхождений переменной ’’щ” в формулу с гёделевым номером щ, ложна. Пусть т = д(Ф(щ)). Тогда sub(m, m) = д^^т^. Допустим, что высказывание Ф(т) истинно. Это высказывание имеет вид Эго(Фзиь(ёп, т, гд) &-’Фт^о)), и его истинность означает, что существует такое число а, для которого истинно высказывание Ф5иб(т, т, а) & -,Фт-(а). Следовательно, а = su6(m,m), и истинно высказывание ->Фт(виЬ(т, т)). Но это означает, что высказывание с номером su6(m,m), т. е. Ф(т), ложно. Полученное противоречие показывает, что высказывание Ф(т) не может быть истинным. Значит, оно ложно. Ложность высказывания 3vo(sub(m, т, г>о) & ^Фт(''и)) означает, что каково бы ни было натуральное число а, если истинно высказывание Ф8иь(т,т,аф то высказывание -|Фт-(а) ложно. В частности, когда а = su6(m,m), получаем, что ложно высказывание ->Фт(виЬ(т, т)). Но это означает, что истинно высказывание Фр(.зиЬ(т, т)), а тогда истинно и высказывание с гёделевым номером su6(m,m), т. е. Ф(т). Опять получили противоречие. Значит, высказывание Ф(т) не истинно и не ложно, чего не может быть. Итак, наше предположение об арифметичности множества Т и существовании формулы ФтДщ) неверно, и на самом деле множество Т неарифметично. Теорема 26.1 доказана.
Теорема 26.2. Множество Т всех истинных высказываний языка формальной арифметики не является перечислимым.
Доказательство. По теореме 24.3, всякое перечислимое множество является арифметическим. В силу теоремы Тарского множество Т неарифметично, значит, оно и неперечислимо. Теорема 26.2 доказана.
Первая теорема Гёделя о неполноте
Теорема 26.2 имеет самое непосредственное отношение к проблеме задания формальной арифметики в виде аксиоматической системы. Аксиоматический метод построения математической теории состоит в том, что некоторые исходные факты этой теории, называемые аксиомами или постулатами, принимаются ’’без доказательства” , а все другие утверждения этой теории выводятся из них путем рассуждений. В 1891 г. итальянский математик Пеано предложил аксиоматику для натурального ряда. На языке формальной арифметики аксиомы Пеано записываются следующим образом:
VtVj/((t + 1) = (у + 1) D х = у);
Vt^(t+ 1) = 0;
Vt(t + 0) = х;
^у(х + (у + 1)) = ((ж + у) + 1);
Мх^х • 0) = 0;
\/х\/у(х • (у + 1)) = ((ж • у) + ж);
Ф(0) &\/ж(Ф(ж) D Ф(ж + 1)) D УжФ(ж).
При этом 7) представляет собой не отдельную аксиому, а схему аксиом: какова бы ни формула Ф(ж), выражение 7) является аксиомой.
В математической логике разработаны средства формального логического вывода, позволяющие из данных аксиом по определенным правилам получать новые высказывания, логически вытекающие из аксиом и называемые теоремами. Одним из таких средств является исчисление предикатов, изучаемое в курсе математической логики. В рамках этого исчисления вводится понятие доказательства как конечной последовательности формул, строящейся по определенным правилам. При этом, если множество всех аксиом разрешимо (как, например, в случае аксиом Пеано), то множество всех доказательств также оказывается разрешимым. Формула Ф считается доказуемой, если существует доказательство, оканчивающееся этой формулой. Правила вывода исчисления предикатов позволяют на основе истинных аксиом доказывать только истинные высказывания. Нетрудно убедиться, что множество всех доказуемых высказываний является перечислимым. Следовательно, в силу теоремы 26.2, оно не совпадает с множеством всех истинных высказываний. Приведенное рассуждение представляет собой доказательство первой теоремы Гёделя о неполноте, которая в упрощенном виде формулируется следующим образом:
Теорема 27.1. Пусть задана аксиоматическая теория в языке формальной арифметики с разрешимым множеством аксиом, в которой все доказуемые высказывания истинны. Тогда существует высказывание Ф, которое является истинным, но не доказуемым.
Как построить конкретное истинное высказывание, которое не доказуемо в данной аксиоматической теории с разрешимым множеством аксиом? Ответ на этот вопрос получается из доказательства следующей теоремы.
Теорема 27.2. Множество Т всех истинных высказываний языка формальной арифметики является продуктивным.
Доказательство. Пусть дано перечислимое подмножество X множества Т. Так как индексное множество 1х множества X перечислимо, то оно арифметично, причем по его гёделеву номеру можно построить формулу Фд- (щ), определяющую множество 1х • Рассмотрим формулу ЕФо(5и6(щ, щ,^о)& “'Фт («о)), которую обозначим Ф(щ). Пусть m = <7(Ф(щ)). Тогда, очевидно, sub(m, m) = </(Ф(т)). Допустим, что высказывание Ф(т) ложно. Оно имеет вид 3vo(sub(m, т, г>о) & “'Фт («о))- Его ложность означает, что каково бы ни было натуральное число а, если истинно высказывание Ф5иб(т, т, а), то высказывание -|Фт(а) ложно. В частности, когда а = su6(m,m), получаем, что ложно высказывание -|Фт(би6(т, т)). Но это означает, что истинно высказывание Фх^виЬ^т, т)), а тогда оказывается, что высказывание с гёделевым номером su6(m,m), т. е. Ф(т), принадлежит множеству X, состоящему только из истинных высказываний. Значит, высказывание Ф(т) истинно и принадлежит множеству Т. С другой стороны, это высказывание означает, что существует такое число а, для которого истинно высказывание Ф5иб(т, т, а) & -|Фт (а). Отсюда следует, что а = su6(m,m), и тогда истинно высказывание -|Фт(би6(т, т)). Но это означает, что высказывание с номером su6(m,m), т. е. Ф(т), не принадлежит множеству X. Итак, по гёделеву номеру перечислимого подмножества 1х множества 1р мы можем эффективно, т. е. с помощью алгоритма, построить число из Т\ X, а именно, в качестве такого числа нужно взять гёделев номер построенной нами формулы Ф(т). Теорема 27.2 доказана.
Теорема 27.2 имеет и другое, более простое доказательство. В силу теоремы 19.1 достаточно доказать, что продуктивное множество К m-сводимо к множеству 1р. Множество К является арифметическим. Пусть Ф^Дщ) — определяющая его формула. Для каждого натурального п положим /(п) = у(Ф^(п)). Множество К m-сводится к множеству 1р посредством функции /. Действительно, п £ К тогда и только тогда, когда формула Ф^(п) истинна, т. е. ее гёделев номер д^Ф^пУ) принадлежит множеству 1р. Приведенное доказательство, однако, не дает явного построения продуктивной функции для множества 1р и в этом смысле уступает предыдущему доказательству.
Задачи.
Найти гёделев номер терма 2.
Найти гёделев номер формулы (2 • 2) = 4.
Пусть Т — множество всех ложных высказываний языка формальной арифметики. Доказать, что множество Т неарифметично.
Доказать, что множество Т продуктивно.
Меры сложности вычислений
В реальных вычислениях даже для вычислимой функции / весьма актуальным является вопрос: ’’Вычислима ли / практически?” Иными словами, существует ли программма, вычисляющая функцию / за время, которым мы располагаем? Конечно, многое зависит от мастерства программиста: неудачно составленная программа может работать очень долго. Однако есть и объективные факторы, влияющие на скорость вычисления функций. Они изучаются в теории сложности вычислений.
Как известно, каждый алгоритм работает по шагам. В рассмотренных нами машинах Тьюринга и машинах с неограниченными регистрами шагом работы может считаться выполнение одной команды. Считая, что каждый шаг выполняется за единицу времени, мы можем определить время вычисления как число шагов алгоритма, совершаемых в процессе этого вычисления. Возможны и другие меры сложности вычисления. После того как выбрана мера сложности вычисления, возникает вопрос о сложности вычисления конкретных функций. В частности, представляется естественной проблема построения ’’наилучшего” алгоритма для вычисления данной функции.
В силу сказанного выше, для каждого натурального числа е и п > 1 определим функцию ten\xi, . . ., жп) как число шагов, сделанное при вычислении значения у^)®!, • • •, ®п) с помощью программы с номером е. (Если значение yen\®i, • • •, ®п) не определено, то значение t^^xy, • • •, кД также считается неопределенным.) Так определенная функция t^ называется сигнализирующей функцией. Отметим следующие простые, но важные свойства сигнализирующей функции /Д':
• Dom(ten^ = Dom^pe^Y,
е для каждого п множество
разрешимо.
Второе из этих свойств явно контрастирует с тем фактом, что множество
{Д, X-!,..., Х^у^Р^Ч®!, . . . , Жп) ~ у}
неразрешимо. При n = 1 вместо te"'1 будем писать просто te.
Следующее понятие будет часто использоваться в формулировках теорем. Пусть задано некоторое свойство М (п), которым может обладать или не обладать каждое натуральное число. Будем говорить, что свойство М(п) выполняется для почти всех п или почти всюду, если
(Эп0)Дп > п0)М(п)
(иными словами, если это свойство выполняется для всех натуральных чисел, кроме конечного их множества).
Следующая теорема показывает, что существуют сколь угодно сложно вычислимые функции.
Теорема 28.1. Пусть b — одноместная тотальная вычислимая функция. Существует такая одноместная тотальная вычислимая функция f, принимающая только значения 0 и 1, что
(Ve)(/ = ре => Д(п) > Ди) почти всюду).
натурального пнатурального пi(n) = <i(n) = <Доказательство. Определим частичную одноместную функцию г следующим образом: для любого
натурального п
натурального п
i(n) = <
i(n) = <
наименьшее i < п такое, что г отличается от всех определенных значений Дт) при т < п, и С(п) < Ь(п);
не определено в противном случае.
Функция г вычислима. Действительно, чтобы проверить, выполняется ли условие /Дп) < Ди), нужно вычислить Дп) и сделать не более Дп) шагов в вычислении уДи). Если за это время вычисление закончилось, то условие /Дп) < Дп) выполнено, в противном случае — нет. Вычислим, например, ДО). Для этого вычислим
6(0) и сделаем не более чем 6(0) шагов в вычислении ^о(О) (т. е. в работе программы с номером 0 на исходном данном 0). Если за это время вычисление закончилось, полагаем г(0) = 0; в противном случае значение г(0) считаем неопределенным. Заметим, что область определения функции г разрешима, и если значение г)к) определено, то г(&) < к.
Покажем, что если число г таково, что /Дт) < 6(т) для бесконечно многих т, то г = г(п) для некоторого п. Пусть
р = 1 + max{fc|«(fc) определено и i < г(^)}
(положим р = 0, если нет ни одного значения г(&) < г). Возьмем такое п > г, что п > р и /Дп) < 6(п). Если г = Дй) для некоторого к < п, то все доказано. Пусть г ф г)к) для всех к < п. Тогда получаем, что г < п, г отличается от всех определенных значений Дт) при т < п и /Дп) < 6(п). Значит, Дп) определено, причем Дп) < г. Но поскольку п > р, то должно быть Дп) > г. Следовательно, Дп) = г, что и требовалось.
Теперь положим для любого натурального п
fW = (fW = (если Дп) определено и ргдпДп) = 0;
fW = (
fW = (
0 в противном случае.
Функция / вычислима. Действительно, как мы уже отметили выше, область определения функции г разрешима, так что с помощью алгоритма можно узнать, определено ли значение Дп). Далее, если это значение определено, то обязательно определено и значение ppn^nY Вычислив его, мы можем узнать, равно ли оно нулю. Таким образом, для любого п мы можем найти значение /(п).
Покажем, что J — искомая функция. Пусть f = ре, т. е. программа с номером е вычисляет функцию /. Для любого п, если значение Дп) определено, то, как видно из задания функции f, е ф i(n). С другой стороны, если бы неравенство 6е(т) < 6(т) выполнялось для бесконечно многих т, то, как мы показали ранее, должно быть е = Дп) для некоторого п. Значит, для почти всех т выполняется неравенство
6е(т) > 6(т),
что и требовалось. Теорема 28.1 доказана.
Можно ли из формулировки теоремы исключить слова ’’почти всюду” и заменить их на ’’для всех п”? Очевидно, нет. Дело в том, что для каждой функции J можно написать программу, которая очень быстро вычисляет значение / в одной конкретной точке а. Пусть, например, /(а) = 1, и пусть программа Р вычисляет функцию J. Составим новую программу Р', вычисляющую функцию /:
5(2)
а) Д(2)
а + 1) Я(1)
а+ 2) 5(1)
а + 3) <7(1,2, stop)
а + 4) Z(2)
Р
(здесь stop — некоторое число, большее числа команд в программе Р'). Очевидно, что если е — номер программы Р', то te)a) = а + 3. Поэтому, если, например, 6(п) = п + 4, то заключение теоремы 28.1 будет неверным для таких функций f и 6 при замене слов ’’почти всюду” на ’’для всех п”.
Время вычисления является лишь одной из возможных мер сложности вычислений. При абстрактном подходе к сложности вычислений мерой вычислительной сложности (одноместных функций) называется семейство одноместных функций Фе (е £ N) со следующими свойствами:
• Вот(Фе) = Вот)(ре);
е множество {(е, х, у)|Фе(т) ~ у} разрешимо.
Очевидно, что рассмотренное выше семейство функций te является мерой вычислительной сложности в этом смысле. Вот другие примеры мер вычислительной сложности:
ФДж) — количество выполнений команд условного перехода при вычислении (ре)х), если это вычисление завершается;
ФДж) — максимальное число, содержащееся в каком-либо регистре МНР за все время вычисления (ре)х), если это вычисление завершается.
При вычислениях на машинах Тьюринга обычно рассматриваются временная сложность, определяемая как число шагов в вычислении, и пространственная сложность, определяемая как длина ленты, использованной в вычислении.
Заметим, что при доказательстве теоремы 28.1 мы использовали только те свойства функции te, которые сформулированы в определении меры вычислительной сложности. Следовательно, эта теорема остается верной при замене С (и) на Фе(п) для любой меры вычислительной сложности Фе.
Теорема о неподвижной точке
В дальнейшем нам понадобится следующая теорема, представляющая и самостоятельный интерес.
Теорема 29.1 (теорема о неподвижной точке). Каковы бы ни были натуральное число т > 1 и тотальная одноместная вычислимая функция J, существует число п такое, что У^) = У"""1 •
Доказательство. Рассмотрим следующую (т + 1)-местную функцию:
-ф(и, Хх,. . . , Хт) ~ ^^^(Тх, . . . , Хтф
Пусть е -гёделев номер функции V', т. е. ^ = Уе™"1 • В силу s-m-n-теоремы (теорема 7.2) существует тотальная вычислимая двуместная функция s (функция Д, в обозначениях упомянутой теоремы) такая, что для любых е, и, хх, . . ., хт имеет место условное равенство ye™"*"1'1 (и,хх, . . ., хт) ~ у™е ^(^i, • • •, хт). В нашем случае, при фиксированном е, положим g(u) = s(e, и). Тогда
ДД)(Ж1’• -Жт)-
Пусть х — гёделев номер композиции функций / и ^, т. е. ^(ж) = Дд(хУ) для любого х. Тогда для любых Xi, . . ., хт имеем:
ДРн^ь • • - Ж™) — р^^хх, ...,хт)~ ^^(хх, ...,хт), и теорема доказана, если взять п = д^иф □
При m = 1 получаем, что для любой тотальной одноместной вычислимой функции f существует ’’неподвижная точка”, т. е. такое число п, что ^/(п) = рщ- Эта теорема имеет многочисленные применения в теории алгоритмов.
Примеры. 1. Вот как, например, с помощью теоремы о неподвижной точке доказывается теорема Райса. Допустим, что индексное множество 1^ нетривиального семейства одноместных вычислимых функций Т разрешимо. Пусть уа £ Т, <рь ^ Т. Если множество Ту разрешимо, то вычислима функция
fX = (fX = (Ь, если х Е 1у; а, если х ^ ly.
fX = (
fX = (
По теореме о неподвижной точке существует число п такое, что ^/(п) = рщ- Пусть п Е Ip, т. е. рп Е Т. Тогда /(п) = Ъ, что невозможно, так как в этом случае рп = ^/(п) = рь ^ Т. Аналогично, если п ^ 1^, т. е. Рп ^ -Г то /(п) = а, что также невозможно, ибо в этом случае рп = ^/(п) = ра £ Т. Значит, неверно ни одно из утверждений п Е Ip и п ^ ly. Полученное противоречие доказывает, что на самом деле множество Ij неразрешимо.
Если / — тотальная одноместная вычислимая функция, то существует такое число п, что Wj^ = Wn. Действительно, по теореме о неподвижной точке существует число п такое, что ^/(п) = Ун- Тогда
И-/Э) = Dom(p^n^ = Пот(р„) = W„.
Существует такое число п, что ^х^рп^х^ = х". Для доказательства этого факта рассмотрим двуместную вычислимую функцию /(т, ж) = х™. По теореме о параметризации существует тотальная одноместная вычислимая функция & такая, что f(m, х) = ^ц-гу^Х) Для любых т,х. По теореме о неподвижной точке существует такое число п, что рцу = УЖ Тогда для любого х имеем: уп(т) = У/Дп))®) = /(пж) = X что и требовалось.
Задачи.
Доказать, что существует такое число п, что а)у„(0) = п; б) рп(п) = п; в) р„ = х^У г) У» = 'ФкУ
Доказать, что существует такое число п, что а)Ж„={п}; б) Ж„ = {п2}; в)Жn = N\{n}.
30. Теорема об ускорении
Пусть Ра и Рь — две программы для вычисления тотальной функции /, причем 2tb(x) < ta(x) для любого х. В этом случае можно сказать, что программа Рь работает в два с лишним раза быстрее программы Ра. Оказывается, что существует тотальная функция /, обладающая следующим свойством: какова бы ни была программа Р для вычисления функции /, существует другая программа, которая работает в два с лишним раза быстрее на почти всех исходных данных. Таким образом, для этой функции не существует ’’наилучшей” программы. Этот факт — частный случай следующей теоремы, доказанной Блюмом:
Теорема 30.1 (теорема об ускорении). Пусть г — тотальная одноместная вычислимая функция. Существует тотальная одноместная вычислимая функция f такая, что по любой программе Pi, вычисляющей функцию f, можно построить другую программу Pj для вычисления f такую, что r(tj(x)) < ti(x) для почти всех х.
Доказательство. Теорему достаточно доказать в случае, когда г — возрастающая функция. Действительно, если г — произвольная тотальная вычислимая функция, рассмотрим функцию г', заданную так: г'(0) = г(0) и
Г г(п + 1), если r(n + 1) > г1 (nVv( r'(n) в противном случае.
Очевидно, что функция т' является возрастающей, вычислима и мажорирует функцию г в том смысле, что г(п) < г'(п) для любого п. Теперь, если г'(^(т)) < Д(т) для почти всех х, то и r(tj(x^ < Д(т) для почти всех х.
Пусть фиксировано натуральное число е. Определим двуместную вычислимую функцию д(и, х) рекурсией по х при фиксированном и. При этом одновременно с вычислением д(и, х) будут строиться вспомогательные конечные множества Си,х- Итак, пусть значения д(и, 0), . . ., д(и, х — 1) и множества Сир, . . ., CU)x-i уже определены. В силу s-m-n-теремы существует тотальная вычислимая двуместная функция s (функция sj в обозначениях упомянутой теоремы) такая, что для любых е, х, у имеет место условное равенство
~ р^х^У).
Зафиксируем такую функцию s. Положим
Си , х — {^ I ^ С i С х Р i ^ С у <^ х Су &г ti ^х^ С г(/5(еу_|_]д(т) -|- ж)),
если значение ^(e ^i^T) определено для всех i = и, . . ., х — 1; в противном случае множество Си,х не определено. Заметим, что если х < и, то Си,х определено и равно 0. Кроме того, если ^(e ^i^T) определено, то можно решить, выполняется ли неравенство Д(т) < г(/5(е>г-+1)(ж) + ж). Теперь определим д(и,х) следующим образом:
у(и, ж) =у(и, ж) =+ шах{уг(т)|г G CU]xV если Си,х определено;
у(и, ж) =
у(и, ж) =
не определено в противном случае.
Заметим, что если множество Си,х определено, то для каждого г 6 Си,х значение уДт) определено, так что в этом случае значение д(и, х) определено.
Итак, д — двуместная вычислимая функция. Вообще-то ее определение зависит от фиксированного в самом начале наших рассуждений числа е. Очевидно, что номер программы, вычисляющей функцию д, может быть вычислен по числу е, т. е. существует такая одноместная тотальная вычислимая функция к, что д(и, х) ~ рц^и, х). В силу теоремы о неподвижной точке (теорема 29.1) существует такое число е, что
д(и,х) ~ р^Чщхф(5)
т. е. так построенная функция при этом фиксированном е сама вычисляется программой с номером е.
Покажем, что в этом случае функция д тотальна. Фиксируем х. Как мы уже отмечали, для и > х множество CU]x определено и пусто, так что д(и, х) = 1. Предположим теперь, что все значения
д(ж, ж), д(ж — 1, ж),.. •, д(и + 1, х)
определены. В силу (5) и определения функции s получаем, что значения
Vs (е^Рз(е,х — 1) (^) , • • • , 9^5(е,-и + 1)(^)
определены. Следовательно, для i = и, . . ,,х — 1 определены значения С(е,г+1)(ж)- Это означает, что мно
жество Си,ж определено; следовательно, определено и значение д(и,х). Таким образом, д(и,х) — тотальная функция.
Положим ди(х) = д(и, х). Тогда ди(х) = д(и,х) = рД (и,х) = р^^Дх)- Положим / = до- Покажем, что
ДЛЯ ВСЯКОГО XДЛЯ ВСЯКОГО XJ является искомой функцией. Зафиксируем число и и убедимся, что функции до и ди отличаются только в конечном числе точек, т. е. д(0,х) = д(и,х) для почти всех х. Из построения множества Си,ж видно, что
ДЛЯ ВСЯКОГО X
ДЛЯ ВСЯКОГО X
Си,ж = Со,х П {и, и + 1, . . . , X — 1}.
Так как по построению все множества Со,х при различных х попарно не пересекаются, то можно найти число
г = тах{ж|(3г < и)г £ СоЛ. Тогда для х > г имеем Cq,x С {и, и + 1, . . ., х — 1}; следовательно, Со,х = Си,х, так что д(0, х) = дД, х) для всех х > г.
Пусть теперь f = р;. Тогда, если j = s(e, г'+ 1), то pj = ps^g^ = y^+i. Докажем, что г(йДт) + т) < /Дж)
для почти всех х. Если бы это было не так, т. е. выполнялось бы неравенство /Дж) < г(/5{ед+1)(ж) + ж) для бесконечно многих х, то нашлось бы х, для которого
О С и У х к i bY Cy<_xCu,y ^ti^x^ У гД5(ед_|_1Дт) Т тД,
т. е. г 6 Со,х. Но тогда из определения функции д следует д(0,х) Д уДж), что невозможно. Полученное
противоречие доказывает, что неравенство г(/Дж) + х) < /Дж) выполняется для почти всех х.
Итак, по данному г, для которого f = рр мы построили такое число j, что функция pj совпадает с J почти всюду и г(/Дж) + х) < ti (ж) для почти всех х. Осталось только программу с номером j переделать в программу для вычисления функции J. Пусть (Уж > u)pj(x) = f(x) и /(m) = Ьт для т < v. Тогда программу Pj несколько модифицируем следующим образом:
5(1,2,/0)
5(2)
Д1/2,к)
2г) 5(2)
2г+ 1) 7(1,2,Д)
2г + 2) Pj
J(l, 1, stop)
Д) Qb0
J(l, 1, stop)
Qb„
J(l, 1, stop)
(Здесь через Qb обозначена программа, помещающая число b в первый регистр.) Пусть j* — номер только что построенной программы. Эта программа вычисляет функцию J. Дополнительные команды увеличивают время вычисления по сравнению с программой Pj не более чем на с шагов, где с — константа, не зависящая от исходного данного х. Таким образом, ДхДЦх) < tj(x) + с. Поскольку г — возрастающая функция, r(tjt (х)) < тДДД + с) < тДДД + х) для х > с. Учитывая также, что r)tj)x) + х) < Дх) для почти всех х, получаем, что г(Д (х)) < Дх) для почти всех х, что и требовалось доказать. Теорема 30.1 доказана.
Литература
Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М., Мир, 1983.
Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М., Физматлит, 1995.
Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М., Мир, 1972.
Мендельсон Э. Введение в математическую логику. М., Наука, 1984.
Успенский В. А. Лекции о вычислимых функциях. М., Физматлит, 1960.
[61 Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М., ФИЗМАТЛИТ, 2002.
Теория алгоритмов
Е. Плиско