Теорема о графике вычислимой функции

теорема о графике вычислимой функции Рекурсивные функции Понятие машины Тьюринга — не единственный известный путь уточнения понятия  алгоритма. В настоящем и следующем параграфах будут рассмотрены еще два способа  такого уточнения: рекурсивные функции и нормальные алгоритмы Маркова. Происхождение рекурсивных функций Всякий алгоритм однозначно сопоставляет допустимым начальным данным результат. Это означает, что с каждым алгоритмом однозначно связана функция, которую он вычисляет.  В предыдущем параграфе были рассмотрены примеры функций, которые вычисляются с  помощью алгоритма, названного машиной Тьюринга. Возникает естественный вопрос, для  всякой ли функции существует вычисляющий ее алгоритм. Учитывая сформулированный  ранее тезис Тьюринга, утверждающий, что функция вычислима с помощью какого­нибудь  алгоритма тогда и только тогда, когда она вычислима с помощью машины Тьюринга,  данный вопрос трансформируется в следующий. Для всякой ли функции можно указать  вычисляющую ее машину Тьюринга? Если нет, то для каких функций существует  вычисляющий их алгоритм (машина Тьюринга), как описать такие, как говорят,  алгоритмически или эффективно вычислимые функции? Исследование этих вопросов привело к созданию в 1930­х гг. теории рекурсивных  функций. При этом класс вычислимых функций (названных здесь рекурсивными) получил  такое описание, которое весьма напомнило процесс построения аксиоматической теории  на базе некоторой системы аксиом. Сначала были выбраны простейшие функции,  эффективная вычисляемость которых была очевидна (своего рода "аксиомы"). Затем  сформулированы некоторые правила (названные операторами), на основе которых можно  строить новые функции из уже имеющихся (своего рода "правила вывода"). Тогда  требуемым классом функций будет совокупность всех функций, получающихся из  простейших с помощью выбранных операторов. Наша цель будет состоять в том, чтобы доказать, что этот класс функций совпадет с классом функций, вычислимых с помощью  машин Тьюринга. Идея доказательства этого утверждения в одну сторону проста: сначала доказать  вычислимость по Тьюрингу простейших функций, а затем вычислимость по Тьюрингу  функций, получающихся из вычислимых по Тьюрингу функций с помощью выбранных  операторов. Основные понятия теории рекурсивных функций и тезис Чёрча Приступим к построению класса рекурсивных функций в соответствии с изложенными  принципами. Напомним, что рассматриваются функции, заданные на множестве  натуральных чисел и принимающие натуральные значения. Функции предполагается брать  частичные, т. е. определенные, вообще говоря, не для всех значений аргументов. В  качестве исходных простейших функций выберем следующие:  (функция следования);  (нуль­функция);  (функции­проекторы,  ). Вычислимость (более того, правильная вычислимость) этих функций с помощью машины  Тьюринга установлена в примерах 32.7 и 32.10. Далее, в качестве операторов, с помощью  которых будут строиться новые функции, выберем следующие три: операторы  суперпозиции, примитивной рекурсии и минимизации. Определение 33.1 (оператор суперпозиции). Будем говорить, что n­местная  функция  помощью оператора суперпозиции, если для всех   получена из m­местной функции   и n­местных функций  , справедливо равенство:  с  Понятие суперпозиции функций и сложной функции хорошо известно, но нас сейчас этот  оператор интересует с точки зрения его взаимоотношений с процессом вычислимости  функций с помощью машин Тьюринга. Теорема 33.2. Если функции   правильно  вычислимы по Тьюрингу, то правильно вычислима и сложная функция (суперпозиция  функций): ▼  Доказательство Определение 33.3. Говорят, что (n+1)­местная функция  функции  если для любых   справедливы равенства:  и (n +2)­местной функции   с помощью оператора примитивной рекурсии,   получена из n­местной  Пара этих равенств называется схемой примитивной рекурсии. Здесь важно отметить то, что, независимо от числа аргументов в  только по одной переменной  ; остальные  схемы примитивной рекурсии зафиксированы и играют роль параметров. Кроме того,  схема примитивной рекурсии выражает каждое значение определяемой функции   не   и  , но и через так называемые предыдущие значения  только через данные функции  определяемой функции  , придется  проделать   вычисление по указанной схеме — для   прежде чем получить значение  , рекурсия ведется  , на момент применения  переменных  . Определение 33.4. Функция называется примитивно рекурсивной, если она может  быть получена из простейших функций  применений операторов суперпозиции и примитивной рекурсии.  с помощью конечного числа  Наконец, введем заключительный, третий, оператор.  получается из (n+1)­местных функций  Определение 33.5 (оператор минимизации). Будем говорить, что n­местная  функция  минимизации, или оператора наименьшего числа, если для любых  равенство  значения  неравны: выполнено тогда и только тогда, когда   с помощью оператора   определены и попарно   и      а   равна  наименьшему значению аргумента  , при котором выполняется последнее равенство.  Используется следующее обозначение: . Коротко говоря, величина В частном случае может быть  Оператор минимизации называется также µ­оператором. Этот оператор предназначен для  порождения следующего важного класса рекурсивных функций. . Тогда  .  Определение 33.6. Функция называется частично рекурсивной, если она может быть  получена из простейших функций  суперпозиции, примитивной рекурсии и µ­оператора. Если функция всюду определена и  частично рекурсивна, то она называется общерекурсивной. (Отметим, что не всегда  частично рекурсивную функцию можно эффективно доопределить до общерекурсивной.)  с помощью конечного числа применений  Ясно, что всякая примитивно рекурсивная функция будет и частично рекурсивной (и  даже общерекурсивной, так как каждая примитивно рекурсивная функция всюду  определена), поскольку для построения частично рекурсивных функций из простейших  используется больше средств, чем для построения примитивно рекурсивных функций. В  то же время класс частично рекурсивных функций шире класса примитивно рекурсивных  функций, так как все примитивно рекурсивные функции всюду определены, а среди  частично рекурсивных функций встречаются и функции не всюду определенные. Понятие частично рекурсивной функции оказалось исчерпывающей формализацией  понятия вычислимой функции. При построении аксиоматической теории высказываний  исходные формулы (аксиомы) и правила вывода выбирались так, чтобы полученные в  теории формулы исчерпали бы все тавтологии алгебры высказываний. К чему же  стремимся мы в теории рекурсивных функций, почему именно так выбрали простейшие  функции и операторы для получения новых функций? Рекурсивными функциями мы  стремимся исчерпать все мыслимые функции, поддающиеся вычислению с помощью  какой­нибудь определенной процедуры механического характера. Подобно тезису Тьюринга, в теории рекурсивных функций выдвигается соответствующая естественно­ научная гипотеза, носящая название тезиса Чёрча: Числовая функция тогда и только тогда алгоритмически (или машинно) вычислима,  когда она частично рекурсивна. И эта гипотеза не может быть доказана строго математически, она подтверждается  практикой, опытом, ибо призвана увязать практику и теорию. Все рассматривавшиеся в  математике конкретные функции, признаваемые вычислимыми в интуитивном смысле,  оказывались частично рекурсивными. Теперь мы рассмотрим более подробно классы примитивно рекурсивных функций и  частично рекурсивных функций и докажем, что все функции из каждого из этих классов  вычислимы на подходящих машинах Тьюринга. Примитивно рекурсивные функции Итак, функция примитивно рекурсивна, если она может быть получена из простейших  функций   с помощью конечного числа применений операторов суперпозиции и  примитивной рекурсии. Рассмотрим ряд примеров примитивно рекурсивных функций. ▼  Примеры 33.7­33.9 Теорема 33.10. Функция, полученная суперпозицией примитивно рекурсивных функций,  сама примитивно рекурсивна.  с помощью конечного числа применений операторов суперпозиции и  Доказательство. В самом деле, компоненты этой функции получены из простейших  функций  примитивной рекурсии. Чтобы получить рассматриваемую функцию, нужно добавить еще  одну суперпозицию. В итоге эта функция также получается из простейших функций в  результате конечного числа применений операторов суперпозиции и примитивной  рекурсии, т.е. является примитивно рекурсивной. Примитивная рекурсивность предикатов Определив ранее понятие предиката, мы отметили, что к этому понятию возможен и еще  один подход. Предикат  функция, заданная на указанных множествах и принимающая значения в двухэлементном  множестве  связанную с ним, а саму функцию называют характеристической функцией предиката  обозначают  . В теории алгоритмов принято различать предикат  , заданный над множествами  . Таким образом, , есть   и функцию,   и  Если  имеет смысл поставить вопрос о ее примитивной рекурсивности.  — функция, входящая в круг наших рассмотрений, и  , то Определение 33.11. Предикат  характеристическая функция   называется примитивно рекурсивным, если его   примитивно рекурсивна. Отметим еще одно важное свойство, связанное с примитивной рекурсивностью функций.  Мы используем его в последующих рассмотрениях. Одним из часто встречающихся,  особенно в теории алгоритмов, способов задания функций является их задание с помощью так называемого оператора условного перехода. Этот оператор по  функциям   строит функцию   и предикату  Нетрудно понять, что с помощью характеристических функций предиката  отрицания   можно выразить следующим образом:  функцию   и его  Из этого выражения вытекает следующее утверждение. Теорема 33.12. Если функции   и предикат   примитивно рекурсивны, то и  функция   с помощью оператора Условного перехода,  примитивно рекурсивна. Этот факт выражают также говоря, что оператор  условного перехода примитивно рекурсивен. , построенная из  Оператор условного перехода может иметь и более общую форму, когда переход носит не двузначный, а многозначный характер и определяется конечным числом  предикатов  , из которых истинен всегда один и только один предикат. Ясно, что и в такой форме оператор условного перехода примитивно рекурсивен, так как и в этом  случае производимую им функцию можно представить в аналогичном виде: Заметим, что это соотношение определяет  истинен: в этом случае   равно нулю.  и в том случае, когда ни один из   не Последнее замечание позволяет доказать примитивную рекур­сивность функций,  заданных на конечных множествах, ибо все их можно задать с помощью оператора  условного перехода. Правда, при этом их придется доопределить с помощью какой­либо  константы на всех остальных натуральных числах, на которых она не определена.  Например, функцию ф, определенную на множестве  равенствами  перехода можно описать так: , с помощью оператора условного      Таким образом,   вне исходной области задания. В заключение обсуждения примитивно рекурсивных функций сделаем два важных  замечания. Во­первых, все примитивно рекурсивные функции всюду определены. Это следует из  того, что всюду определены простейшие функции, а операторы суперпозиции и  примитивной рекурсии это свойство сохраняют. Во­вторых, строго говоря, мы имеем дело не с функциями, а с их примитивно  рекурсивными описаниями. Различие здесь точно такое же, как и различие между  булевыми функциями и их представлениями в виде формул. Примитивно рекурсивные  описания также разбиваются на классы эквивалентности: в один класс входят все  описания, задающие одну и ту же функцию. Но задача распознавания эквивалентности  примитивно рекурсивных описаний являет собой еще один пример алгоритмически  неразрешимой задачи. Вычислимость по Тьюрингу примитивно рекурсивных функций Теперь мы готовы к тому, чтобы сделать еще один шаг на пути (в каком­то смысле  аксиоматического) описания всех функций, вычислимых с помощью машины Тьюринга.  Мы докажем, что всякая примитивно рекурсивная функция вычислима с помощью  машины Тьюринга. Для этого остается доказать следующую теорему. Теорема 33.13. Функция  вычислимых на машине Тьюринга функций  Тьюринга. , возникающая примитивной рекурсией из правильно   и  , сама правильно вычислима на машине ▼  Доказательство Следствие 33.14. Всякая примитивно рекурсивная функция вычислима по Тьюрингу. Доказательство. Утверждение следует (ввиду определения 33.4 примитивно  рекурсивной функции) из вычислимости по Тьюрингу простейших функций и свойств  сохранения такой вычислимости операторами суперпозиции (теорема 33.2) и  примитивной рекурсии (теорема 33.13). Функции Аккермана Напомним, что мы поставили задачу охарактеризовать вычислимые (с помощью какого­ либо алгоритма) функции. Учитывая тезис Тьюринга, под алгоритмом достаточно  понимать машину Тьюринга. После того как в предыдущем пункте было доказано, что  всякая примитивно рекурсивная функция вычислима (по Тьюрингу), возникает обратный  вопрос: исчерпывается ли класс вычислимых (по Тьюрингу) функций примитивно  рекурсивными функциями, т.е. всякая ли вычислимая (по Тьюрингу) функция будет  непременно примитивно рекурсивной? Применив теоретико­множественное понятие о мощности, достаточно легко ответить  отрицательно на более общий вопрос: исчерпывается ли класс всех функций примитивно  рекурсивными функциями, т. е. все ли функции являются примитивно рекурсивными? Теорема 33.15. Существуют функции, не являющиеся примитивно рекурсивными. Доказательство. В самом деле, нетрудно понять, что множество всех примитивно  рекурсивных функций счетно. Это объясняется тем, что каждая примитивно рекурсивная  функция имеет конечное описание, т.е. задается конечным словом в некотором  (фиксированном для всех функций) алфавите. Множество всех конечных слов счетно. Поэтому и примитивно рекурсивных функций имеется не более, чем счетное множество.  В то же время множество всех функций даже от одного аргумента из   в  мощность континуума. Тем более, континуально множество функций из  конечного числа аргументов. Таким образом непременно существуют функции, не  являющиеся примитивно рекурсивными.  имеет   в   от любого  Отрицательным будет также ответ и на более узкий вопрос, поставленный в предыдущем  пункте: все ли вычислимые (а в силу тезиса Тьюринга — вычислимые по Тьюрингу)  функции можно описать как примитивно рекурсивные? Чтобы это установить,  необходимо привести пример вычислимой функции, не являющейся примитивно  рекурсивной. Идея примера состоит в том, чтобы построить такую вычислимую функцию, которая обладала бы свойством, каким не обладает ни одна примитивно рекурсивная  функция. Таким свойством может служить скорость роста функции. Итак, необходимо  указать такую вычислимую функцию, которая растет быстрее любой примитивно  рекурсивной функции и поэтому примитивно рекурсивной не является. Пример 33.16. Искомая функция конструируется с помощью последовательности  вычислимых функций, в которой каждая функция растет существенно быстрее  предыдущей. ▼  Доказательство Оператор минимизации Это — оператор наименьшего числа в определении 33.5. В более общем виде его можно  определить как оператор, применяемый к произвольному (n+1)­местному этой функции на наборе аргументов   и дающий в результате n­местную функцию  предикату  Значение  из таких чисел  , что высказывание  обозначается  то значение функции  означает, что оператор минимизации может породить частичную, т. е. не всюду  определенную функцию.) Таким образом,  минимизации называется также оператором наименьшего числа, или µ­оператором.  не определено. (Это   на этом наборе   истинно. Оно  . Если же наименьшего среди таких чисел не существует,  .   равно наименьшему  . Оператор   (заданный над  Предикат  минимизации, может быть сконструирован из двух числовых функций следующим  ". Так  образом: " что оператор минимизации можно рассматривать как оператор, заданный на множестве  числовых функций и принимающий значения в нем же. ), к которому при. меняется оператор  ", или из одной: " В этом своем качестве оператор минимизации является удобным средством для  построения обратных функций. Действительно, функция    (наименьший   такой, что  применении к одноместным функциям оператор минимизации иногда называют  оператором обращения.) ) является обратной для функции  . (Поэтому в  Рассмотрим примеры действия оператора минимизации для получения обратных  функций. ▼  Примеры 33.17­33.18 Общерекурсивные и частично рекурсивные функции Итак, функция называется частично рекурсивной (определение 33.6), если она может быть построена из простейших функций  суперпозиции, примитивной рекурсии и µ­оператора. Если функция всюду определена и  частично рекурсивна, то она называется общерекурсивной.  с помощью конечного числа применений  Мы уже отмечали, что класс частично рекурсивных функций шире класса примитивно  рекурсивных функций, так как все примитивно рекурсивные функции всюду определены,  а среди частично рекурсивных функций встречаются функции, не всюду определенные,  например функции  например, нигде не определенная функция  общерекурсивной, но не примитивно рекурсивной функции может служить и функция  Аккермана  , рассмотренные в примерах 33.17, 33.18, а также,  . Примером   и  . Продолжим теперь продвижение к поставленной цели — к описанию всех функций,  вычислимых на машинах Тьюринга. Следующий шаг — доказательство того, что все  частично рекурсивные Функции вычислимы по Тьюрингу. Вычислимость по Тьюрингу частично рекурсивных функций Теорема 33.19. Если функция  функция  функции   правильно вычислима на машине Тьюринга, то и  . получающаяся с помощью оператора минимизации из  , также правильно вычислима на машине Тьюринга. ▼  Доказательство Следствие 33.20. Всякая частично рекурсивная функция вычислима по Тьюрингу. Доказательство. Итак, поскольку оператор минимизации сохраняет свойство  вычислимости по Тьюрингу (этим же свойством, как было установлено выше, обладают и  операторы суперпозиции и примитивной рекурсии), простейшие функции  вычислимы по Тьюрингу, а всякая частично рекурсивная функция получается из  простейших с помощью применения конечного числа раз трех указанных операторов, то  всякая частично рекурсивная функция вычислима по Тьюрингу.   Частичная рекурсивность функций, вычислимых по Тьюрингу Наконец мы расширили класс вычислимых по Тьюрингу функций до таких размеров, что  он исчерпывает класс всех вычислимых по Тьюрингу функций. Это нам и предстоит  доказать. Другими словами, мы намерены доказать, что вычислимы по Тьюрингу лишь  частично рекурсивные функции, т.е. если функция вычислима по Тьюрингу, то она  частично рекурсивна. Еще точнее, по функциональной схеме (программе) машины  Тьюринга, вычисляющей функцию  этой функции. Эта теорема впервые была доказана Тьюрингом. , можно построить рекурсивное описание  Теорема 33.21. Если функция вычислима по Тьюрингу, то она частично рекурсивна. ▼  Доказательство Соединив вместе следствие 33.20 и теорему 33.21, приходим к следующей теореме. Теорема 33.22. Функция вычислима по Тьюрингу тогда и только тогда, когда она  частично рекурсивна. Итог рассмотрений настоящей лекции состоит в том, что мы дали некую альтернативную  характеристику вычислимым по Тьюрингу функциям: это те и только те функции,  которые частично рекурсивны. Другими словами, класс функций, вычислимых по  Тьюрингу, совпадает с классом частично рекурсивных функций. Совпадение этих двух  классов вычислимых функций, в основе построения которых лежали совершенно разные  подходы к формализации понятия вычислимости функции, говорит о том, что эти  подходы оказались весьма состоятельными, и служит косвенным подтверждением того,  что как тезис Тьюринга, так и тезис Чёрча не только не безосновательны, но и имеют все  права на признание. 1. Вычислимые функции, разрешимые множества, определения перечислимого  множества. Теорема Поста. Перечислимые множества как проекции разрешимых.  Вычислимость функции и перечислимость ее графика. Универсальная функция.  Вычислимая функция, которую нельзя доопределить до всюду определенной.  Пример перечислимого, но неразрешимого множества. 2. ­сведения, другие примеры неразрешимых множеств. Последовательность  Шпеккера. Теорема Успенского­Райса. Теорема Клини о неподвижной точке.  Программа, печатающая свой текст. Доказательство теоремы Клини для  искусственного языка программирования. Главные универсальные функции. Вывод  теоремы Успенского­Райса из теоремы Клини. 3. Машины Тьюринга. Неразрешимость проблемы равенства слов в полугруппе  (выводимости в одностороннем и двустороннем ассоциативном исчислении).  Предикатные формулы (формулы I­го порядка). Интерпретации. 4. Выразимость в арифметике. Арифметичность графика вычислимой функции.  Арифметическая иерархия. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя. 5. Недетерминированные машины Тьюринга. Определения класса NP. Примеры.  Сведения по Карпу. Понятние полноты. Полнота задачи об ограниченной остановке. Полнота задачи SAT и 3­SAT. 6. NP­задачи поиска. Сведения по Куку. Сведение задач поиска к задачам  распознавания. Оптимальный алгоритм для NP­задач поиска. Класс PSPACE и  полная задача в ней. Теорема Ладнера о не NP­полном языке в классе NP. 7. Теоремы об иерархии по времени. Полиномиальная иерархия. Простейшие  свойства, полные задачи в  иерархии.  и в  . Оракульное определение полиномиальной  8. Булевы схемы. Вычисления с подсказкой. Класс P/poly. Включение P в P/poly.  Существование функций большой схемной сложности. Теорема Карпа­Липтона.  Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана). 9. Вероятностная машина Тьюринга. Классы BPP и RP. Лемма Шварца­Зиппеля и  вероятностный тест равенства двух многочленов. Понижение ошибки в классе BPP,  BPP содержится в P/poly, BPP содержится в  . 10.Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма  графов и для квадратичных невычетов. Теорема Шамира (IP = PSPACE) и ее  следствия. 11.Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном  покрытии. Вероятностно проверяемые доказательства. Формулировка PCP­ теоремы. Эквивалентные формулировки.