Основы теории вычислимых функций

Вычислимость, разрешимость и перечислимость

Разбить на страницы
Показывать лекцию целиком

Вычислимые функции

Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм A, что

  • если f(n) определено для некоторого натурального n, то алгоритм A останавливается на входе n и печатает f(n) ;
  • если f(n) не определено, то алгоритм A не останавливается на входе n.
    •

    Несколько замечаний по поводу этого определения:

  • Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определенная функция вычислима (в качестве A надо взять программу, которая всегда зацикливается).
  • Можно было бы изменить определение, сказав так: " если f(n) не определено, то либо алгоритм A не останавливается, либо останавливается, но ничего не печатает ". На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).

  • Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0,1} ), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, " конструктивные объекты ". Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.

    Для функций, скажем, с действительными аргументами и значениями понятие вычислимости требует специального определения. Здесь ситуация сложнее, определения могут быть разными, и мы о вычислимости таких функций говорить не будем. Отметим только, что, например, синус (при разумном определении вычислимости) вычислим, а функция sign(x), равная -1, 0 и 1 при x < 0, x = 0 и x > 0 соответственно - нет. Точно так же требует специального определения вычислимость функций, аргументами которых являются бесконечные последовательности нулей и единиц и т.п.

  • Несколько десятилетий назад понятие алгоритма требовало специального разъяснения. Сейчас (" компьютерная грамотность "?) такие объяснения все равно никто читать не будет, поскольку и так ясно, что такое алгоритм. Но все же надо соблюдать осторожность, чтобы не принять за алгоритм то, что им не является. Вот пример неверного рассуждения:

    " Докажем", что всякая вычислимая функция f с натуральными аргументами и значениями может быть продолжена до всюду определенной вычислимой функции g: N -> N . В самом деле, если f вычисляется алгоритмом A, то следующий алгоритм B вычисляет функцию g, продолжающую f: " если A останавливается на n, то B дает тот же результат, что и A ; если A не останавливается на n, то B дает результат (скажем) 0 ". (В чем ошибка в этом рассуждении?)

    •

    Разрешимые множества

    Множество натуральных чисел X называется разрешимым, если существует алгоритм, который по любому натуральному n определяет, принадлежит ли оно множеству X.

    Другими словами, X разрешимо, если его характеристическая функция $$\chi (n) = (if n \in X then 1 else 0 fi)$$ вычислима.

    Очевидно, пересечение, объединение и разность разрешимых множеств разрешимы. Любое конечное множество разрешимо.

    Аналогично определяют разрешимость множеств пар натуральных чисел, множеств рациональных чисел и т.п.

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

    Отметим тонкий момент: можно доказать разрешимость множества неконструктивно, не предъявляя алгоритма. Вот традиционный пример: множество тех n, для которых в числе $$\pi$$ есть не менее n девяток подряд, разрешимо. В самом деле, это множество содержит либо все натуральные числа, либо все натуральные числа вплоть до некоторого. В обоих случаях оно разрешимо. Тем не менее мы так и не предъявили алгоритма, который по n узнавал бы, есть ли в $$\pi$$ не менее n девяток подряд.

  • Использованы ли в этом рассуждении какие-то свойства числа $$\pi?$$ Что изменится, если заменить слова " не менее n девяток" на " ровно n девяток (окруженных не-девятками)"?
    •

    Существуют ли неразрешимые множества ? Существуют просто потому, что алгоритмов (и поэтому разрешимых подмножеств натурального ряда) счетное число, а всех подмножеств натурального ряда несчетное число. Более конкретные примеры мы еще построим.

    Перечислимые множества

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

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

    Существует много эквивалентных определений перечислимого множества. Вот некоторые из них:

  • Множество перечислимо, если оно есть область определения вычислимой функции.
  • Множество перечислимо, если оно есть область значений вычислимой функции.
  • Множество X перечислимо, если его (как иногда говорят) " полухарактеристическая " функция, равная 0 на элементах X и не определенная вне X, вычислима.
    •

    Чтобы доказать эквивалентность этих определений, воспользуемся возможностью пошагового исполнения алгоритма.

    Пусть X перечисляется некоторым алгоритмом A. Покажем, что полухарактеристическая функция множества X вычислима. В самом деле, алгоритм ее вычисления таков: получив на вход число n, пошагово выполнять алгоритм A, ожидая, пока он напечатает число n. Как только он это сделает, выдать на выход 0 и закончить работу.

    Наоборот, пусть X есть область определения (вычислимой) функции f, вычисляемой некоторым алгоритмом B. Тогда X перечисляется таким алгоритмом A:

    Параллельно запускать B на входах 0,1,2,..., делая все больше шагов работы алгоритма B (сначала один шаг работы на входах 0 и 1 ; потом по два шага работы на входах 0,1,2, потом по три на входах 0,1,2,3 и так далее). Все аргументы, на которых алгоритм B заканчивает работу, печатать по мере обнаружения.

    Итак, мы установили эквивалентность исходного определения определениям 1 и 3 . Если в только что приведенном описании алгоритма A печатать не аргументы, на которых B заканчивает работу, а результаты этой работы, то получается алгоритм, перечисляющий область значений функции f. Осталось еще убедиться, что всякое перечислимое множество есть область значений вычислимой функции. Это можно сделать, например, так: пусть X есть область определения вычислимой функции, вычисляемой некоторым алгоритмом A. Тогда X есть область значений функции

    $$b(x)=\left\{ \begin{aligned} x,\ \text{если $A$ заканчивает работу на $x$},\\ \text{не определено в противном случае}. \end{aligned} \right.$$

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

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

    В самом деле, пусть перечислимое множество X, перечисляемое алгоритмом A, непусто. Возьмем в нем какой-то элемент x0. Теперь рассмотрим такую всюду определенную функцию a: если на n -м шаге работы алгоритма A появляется число t, то положим a(n)=t ; если же ничего не появляется, то положим a(n)=x0. (Мы предполагаем, что на данном шаге работы алгоритма может появиться только одно число в противном случае работу надо разбить на более мелкие шаги.)

    Заметим, что это рассуждение неконструктивно имея алгоритм A, мы можем не знать, пусто ли перечисляемое им множество или нет.

    Теорема 1. Пересечение и объединение перечислимых множеств перечислимы.

    Если X и Y перечисляются алгоритмами A и B, то их объединение перечисляется алгоритмом, который параллельно выполняет по шагам A и B и печатает все, что печатают A и B. С пересечением немного сложнее результаты работы A и B надо накапливать и сверять друг с другом; что появится общего печатать.

      4. Проведите это рассуждение, используя какое-либо другое эквивалентное определение перечислимости.

    Как мы увидим, дополнение перечислимого множества не обязано быть перечислимым.

      5. Иногда говорят о так называемых " недетерминированных алгоритмах " (оксюморон, но распространенный) такой алгоритм включает в себя команды типа

    n := произвольное натуральное число

    (достаточно, впрочем, команды " n := 0 или 1 ", так как произвольное число можно формировать по битам). Недетерминированный алгоритм (при одном и том же входе) может действовать по-разному, в зависимости от того, какие " произвольные " числа будут выбраны. Докажите, что перечислимое множество можно эквивалентно определить как множество чисел, которые могут появиться на выходе недетерминированного алгоритма (при фиксированном входе).

      6. Докажите, что если множества $$A \subset N$$ и $$B \subset N$$ перечислимы, то их декартово произведение $$A x B \subset N x N$$ также перечислимо.

    Перечислимые и разрешимые множества

    Теорема 2. Всякое разрешимое множество натуральных чисел перечислимо. Если множество A и его дополнение (до множества всех натуральных чисел) перечислимы, то A разрешимо.

    Если принадлежность числа к множеству A можно проверить некоторым алгоритмом, то A и его дополнение перечислимы: надо по очереди проверять принадлежность чисел 0,1,2,... и печатать те из них, которые принадлежат A (или те, которые не принадлежат A ).

    В другую сторону: если у нас есть алгоритм, перечисляющий A, а также другой алгоритм, перечисляющий дополнение к A, то для выяснения принадлежности заданного числа n к A надо запустить оба эти алгоритма и ждать, пока один из них напечатает n (мы знаем, что рано или поздно ровно один из них это сделает). Посмотрев, какой алгоритм это сделал, мы узнаем, лежит ли n в A.

    Этот факт называют теоремой Поста

    Она говорит, что разрешимые множества это перечислимые множества с перечислимыми дополнениями. Напротив, перечислимые множества можно определить через разрешимые:

    Теорема 3. Множество P натуральных чисел перечислимо тогда и только тогда, когда оно является проекцией некоторого разрешимого множества Q пар натуральных чисел. (Проекция получается, если от пар оставить их первые компоненты: $$x\hm\in P \hm\Leftrightarrow \exists y (\langle x,y\rangle \hm\in Q)$$.)

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

    Напротив, если P перечислимое множество, перечисляемое алгоритмом A, то оно есть проекция разрешимого множества Q, состоящего из всех таких пар $$\langle x,n\rangle$$, что x появляется в течении первых n шагов работы алгоритма A. (Это свойство, очевидно, разрешимо.)

    Перечислимость и вычислимость

    Мы видели, что перечислимое множество можно определить в терминах вычислимых функций (например, как область определения вычислимой функции). Можно сделать и наоборот:

    Теорема 4. Функция f с натуральными аргументами и значениями вычислима тогда и только тогда, когда ее график

    $$F=\{\langle x, y\rangle \mid \text{$f(x)$ определено и равно $y$}\}$$

    является перечислимым множеством пар натуральных чисел.

    Пусть f вычислима. Тогда существует алгоритм, перечисляющий ее область определения, то есть печатающий все x, на которых f определена. Если теперь для каждого из таких x вычислять еще и значение f(x), получим алгоритм, перечисляющий множество F.

    Напротив, если имеется алгоритм, перечисляющий F, то функция f вычисляется таким алгоритмом: имея на входе n, ждем появления в F пары, первый член которой равен n ; как только такая пара появилась, печатаем ее второй член и кончаем работу.

    Пусть f частичная функция с натуральными аргументами и значениями. Образ множества A при f определяется как множество всех чисел f(n), для которых $$n \in A$$ и f(n) определено. Прообраз множества A при f определяется как множество всех тех n, при которых f(n) определено и принадлежит A.

    Теорема 5. Прообраз и образ перечислимого множества при вычислимой функции перечислимы.

    В самом деле, прообраз перечислимого множества A при вычислимой функции f можно получить так: взять график f, пересечь его с перечислимым множеством N x A и спроектировать на первую координату. Рассуждение для образов аналогично, только координаты меняются местами.

      7. Пусть F перечислимое множество пар натуральных чисел. Докажите. что существует вычислимая функция f, определенная на тех и только тех x, для которых найдется y, при котором $$\langle x,y\rangle\hm\in F$$, причем значение f(x) является одним из таких y. (Это утверждение называют иногда теоремой об униформизации.)

      8. Даны два пересекающихся перечислимых множества X и Y. Докажите, что найдутся непересекающиеся перечислимые множества $$X' \subset X$$ и $$Y' \subset Y$$, для которых $$X' \cup Y' = X \cup Y$$.

      9. Диофантовым называется уравнение, имеющее вид P(x1,...,xn)=0, где P многочлен с целыми коэффициентами. Докажите, что множество диофантовых уравнений, имеющих целые решения, перечислимо. (Оно неразрешимо: в этом состоит известный результат Ю.В.Матиясевича, явившийся решением знаменитой " 10-й проблемы Гильберта".)

      10. Не ссылаясь на доказательство теоремы Ферма, покажите, что множество всех показателей n, для которых существует решение уравнения xn + yn = zn в целых положительных числах, перечислимо. (Как теперь известно, это множество содержит лишь числа 1 и 2.)

      11. Покажите, что всякое бесконечное перечислимое множество можно записать в виде {a(0), a(1), a(2),...}, где a вычислимая функция, все значения которой различны. (Указание: в ходе перечисления удаляем повторения.)

      12. Покажите, что всякое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество. (Указание: воспользуемся предыдущей задачей и выберем возрастающую подпоследовательность.)

      13. Покажите, что для всякой вычислимой функции f существует вычислимая функция, являющаяся " псевдообратной " к f в следующем смысле: область определения g совпадает с областью значений f, и при этом f(g(f(x)))=f(x) для всех x, при которых f(x) определено.

      14. Действительное число $$\alpha$$ называется вычислимым, если существует вычислимая функция a, которая по любому рациональному $$\varepsilon > 0$$ дает рациональное приближение к $$\alpha$$ с ошибкой не более $$\varepsilon,$$ т.е. $$|\alpha - a(\varepsilon )| <= \varepsilon$$ для любого рационального $$\varepsilon > 0$$. (Рациональное число является конструктивным объектом, так что понятие вычислимости не требует специального уточнения.)

  • Докажите, что число $$\alpha$$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $$\alpha,$$ разрешимо.
  • Докажите, что число $$\alpha$$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима.
  • Докажите, что число $$\alpha$$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $$\alpha$$ (последнее означает, что можно алгоритмически указать N по $$\varepsilon$$ в стандартном $$\varepsilon$$ - N -определении сходимости.)
  • Покажите, что сумма, произведение, разность и частное вычислимых действительных чисел вычислимы. Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
  • Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых действительных чисел вычислим.
  • Действительное число $$\alpha$$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $$\alpha,$$ перечислимо. (Перечислимость сверху определяется аналогично.) Докажите, что число $$\alpha$$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
  • Докажите, что действительное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
    •

    Дальнейшие свойства вычислимых действительных чисел см. в задаче 23.

    Страницы:

    Вычислимые функции

    Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм A, что

  • если f(n) определено для некоторого натурального n, то алгоритм A останавливается на входе n и печатает f(n) ;
  • если f(n) не определено, то алгоритм A не останавливается на входе n.
    •

    Несколько замечаний по поводу этого определения:

  • Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определенная функция вычислима (в качестве A надо взять программу, которая всегда зацикливается).
  • Можно было бы изменить определение, сказав так: " если f(n) не определено, то либо алгоритм A не останавливается, либо останавливается, но ничего не печатает ". На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).

  • Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0,1} ), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, " конструктивные объекты ". Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.

    Для функций, скажем, с действительными аргументами и значениями понятие вычислимости требует специального определения. Здесь ситуация сложнее, определения могут быть разными, и мы о вычислимости таких функций говорить не будем. Отметим только, что, например, синус (при разумном определении вычислимости) вычислим, а функция sign(x), равная -1, 0 и 1 при x < 0, x = 0 и x > 0 соответственно - нет. Точно так же требует специального определения вычислимость функций, аргументами которых являются бесконечные последовательности нулей и единиц и т.п.

  • Несколько десятилетий назад понятие алгоритма требовало специального разъяснения. Сейчас (" компьютерная грамотность "?) такие объяснения все равно никто читать не будет, поскольку и так ясно, что такое алгоритм. Но все же надо соблюдать осторожность, чтобы не принять за алгоритм то, что им не является. Вот пример неверного рассуждения:

    " Докажем", что всякая вычислимая функция f с натуральными аргументами и значениями может быть продолжена до всюду определенной вычислимой функции g: N -> N . В самом деле, если f вычисляется алгоритмом A, то следующий алгоритм B вычисляет функцию g, продолжающую f: " если A останавливается на n, то B дает тот же результат, что и A ; если A не останавливается на n, то B дает результат (скажем) 0 ". (В чем ошибка в этом рассуждении?)

    •

    Разрешимые множества

    Множество натуральных чисел X называется разрешимым, если существует алгоритм, который по любому натуральному n определяет, принадлежит ли оно множеству X.

    Другими словами, X разрешимо, если его характеристическая функция $$\chi (n) = (if n \in X then 1 else 0 fi)$$ вычислима.

    Очевидно, пересечение, объединение и разность разрешимых множеств разрешимы. Любое конечное множество разрешимо.

    Аналогично определяют разрешимость множеств пар натуральных чисел, множеств рациональных чисел и т.п.

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

    Отметим тонкий момент: можно доказать разрешимость множества неконструктивно, не предъявляя алгоритма. Вот традиционный пример: множество тех n, для которых в числе $$\pi$$ есть не менее n девяток подряд, разрешимо. В самом деле, это множество содержит либо все натуральные числа, либо все натуральные числа вплоть до некоторого. В обоих случаях оно разрешимо. Тем не менее мы так и не предъявили алгоритма, который по n узнавал бы, есть ли в $$\pi$$ не менее n девяток подряд.

  • Использованы ли в этом рассуждении какие-то свойства числа $$\pi?$$ Что изменится, если заменить слова " не менее n девяток" на " ровно n девяток (окруженных не-девятками)"?
    •

    Существуют ли неразрешимые множества ? Существуют просто потому, что алгоритмов (и поэтому разрешимых подмножеств натурального ряда) счетное число, а всех подмножеств натурального ряда несчетное число. Более конкретные примеры мы еще построим.

    Перечислимые множества

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

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

    Существует много эквивалентных определений перечислимого множества. Вот некоторые из них:

  • Множество перечислимо, если оно есть область определения вычислимой функции.
  • Множество перечислимо, если оно есть область значений вычислимой функции.
  • Множество X перечислимо, если его (как иногда говорят) " полухарактеристическая " функция, равная 0 на элементах X и не определенная вне X, вычислима.
    •

    Чтобы доказать эквивалентность этих определений, воспользуемся возможностью пошагового исполнения алгоритма.

    Пусть X перечисляется некоторым алгоритмом A. Покажем, что полухарактеристическая функция множества X вычислима. В самом деле, алгоритм ее вычисления таков: получив на вход число n, пошагово выполнять алгоритм A, ожидая, пока он напечатает число n. Как только он это сделает, выдать на выход 0 и закончить работу.

    Наоборот, пусть X есть область определения (вычислимой) функции f, вычисляемой некоторым алгоритмом B. Тогда X перечисляется таким алгоритмом A:

    Параллельно запускать B на входах 0,1,2,..., делая все больше шагов работы алгоритма B (сначала один шаг работы на входах 0 и 1 ; потом по два шага работы на входах 0,1,2, потом по три на входах 0,1,2,3 и так далее). Все аргументы, на которых алгоритм B заканчивает работу, печатать по мере обнаружения.

    Итак, мы установили эквивалентность исходного определения определениям 1 и 3 . Если в только что приведенном описании алгоритма A печатать не аргументы, на которых B заканчивает работу, а результаты этой работы, то получается алгоритм, перечисляющий область значений функции f. Осталось еще убедиться, что всякое перечислимое множество есть область значений вычислимой функции. Это можно сделать, например, так: пусть X есть область определения вычислимой функции, вычисляемой некоторым алгоритмом A. Тогда X есть область значений функции

    $$b(x)=\left\{ \begin{aligned} x,\ \text{если $A$ заканчивает работу на $x$},\\ \text{не определено в противном случае}. \end{aligned} \right.$$

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

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

    В самом деле, пусть перечислимое множество X, перечисляемое алгоритмом A, непусто. Возьмем в нем какой-то элемент x0. Теперь рассмотрим такую всюду определенную функцию a: если на n -м шаге работы алгоритма A появляется число t, то положим a(n)=t ; если же ничего не появляется, то положим a(n)=x0. (Мы предполагаем, что на данном шаге работы алгоритма может появиться только одно число в противном случае работу надо разбить на более мелкие шаги.)

    Заметим, что это рассуждение неконструктивно имея алгоритм A, мы можем не знать, пусто ли перечисляемое им множество или нет.

    Теорема 1. Пересечение и объединение перечислимых множеств перечислимы.

    Если X и Y перечисляются алгоритмами A и B, то их объединение перечисляется алгоритмом, который параллельно выполняет по шагам A и B и печатает все, что печатают A и B. С пересечением немного сложнее результаты работы A и B надо накапливать и сверять друг с другом; что появится общего печатать.

      4. Проведите это рассуждение, используя какое-либо другое эквивалентное определение перечислимости.

    Как мы увидим, дополнение перечислимого множества не обязано быть перечислимым.

      5. Иногда говорят о так называемых " недетерминированных алгоритмах " (оксюморон, но распространенный) такой алгоритм включает в себя команды типа

    n := произвольное натуральное число

    (достаточно, впрочем, команды " n := 0 или 1 ", так как произвольное число можно формировать по битам). Недетерминированный алгоритм (при одном и том же входе) может действовать по-разному, в зависимости от того, какие " произвольные " числа будут выбраны. Докажите, что перечислимое множество можно эквивалентно определить как множество чисел, которые могут появиться на выходе недетерминированного алгоритма (при фиксированном входе).

      6. Докажите, что если множества $$A \subset N$$ и $$B \subset N$$ перечислимы, то их декартово произведение $$A x B \subset N x N$$ также перечислимо.

    Перечислимые и разрешимые множества

    Теорема 2. Всякое разрешимое множество натуральных чисел перечислимо. Если множество A и его дополнение (до множества всех натуральных чисел) перечислимы, то A разрешимо.

    Если принадлежность числа к множеству A можно проверить некоторым алгоритмом, то A и его дополнение перечислимы: надо по очереди проверять принадлежность чисел 0,1,2,... и печатать те из них, которые принадлежат A (или те, которые не принадлежат A ).

    В другую сторону: если у нас есть алгоритм, перечисляющий A, а также другой алгоритм, перечисляющий дополнение к A, то для выяснения принадлежности заданного числа n к A надо запустить оба эти алгоритма и ждать, пока один из них напечатает n (мы знаем, что рано или поздно ровно один из них это сделает). Посмотрев, какой алгоритм это сделал, мы узнаем, лежит ли n в A.

    Этот факт называют теоремой Поста

    Она говорит, что разрешимые множества это перечислимые множества с перечислимыми дополнениями. Напротив, перечислимые множества можно определить через разрешимые:

    Теорема 3. Множество P натуральных чисел перечислимо тогда и только тогда, когда оно является проекцией некоторого разрешимого множества Q пар натуральных чисел. (Проекция получается, если от пар оставить их первые компоненты: $$x\hm\in P \hm\Leftrightarrow \exists y (\langle x,y\rangle \hm\in Q)$$.)

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

    Напротив, если P перечислимое множество, перечисляемое алгоритмом A, то оно есть проекция разрешимого множества Q, состоящего из всех таких пар $$\langle x,n\rangle$$, что x появляется в течении первых n шагов работы алгоритма A. (Это свойство, очевидно, разрешимо.)

    Перечислимость и вычислимость

    Мы видели, что перечислимое множество можно определить в терминах вычислимых функций (например, как область определения вычислимой функции). Можно сделать и наоборот:

    Теорема 4. Функция f с натуральными аргументами и значениями вычислима тогда и только тогда, когда ее график

    $$F=\{\langle x, y\rangle \mid \text{$f(x)$ определено и равно $y$}\}$$

    является перечислимым множеством пар натуральных чисел.

    Пусть f вычислима. Тогда существует алгоритм, перечисляющий ее область определения, то есть печатающий все x, на которых f определена. Если теперь для каждого из таких x вычислять еще и значение f(x), получим алгоритм, перечисляющий множество F.

    Напротив, если имеется алгоритм, перечисляющий F, то функция f вычисляется таким алгоритмом: имея на входе n, ждем появления в F пары, первый член которой равен n ; как только такая пара появилась, печатаем ее второй член и кончаем работу.

    Пусть f частичная функция с натуральными аргументами и значениями. Образ множества A при f определяется как множество всех чисел f(n), для которых $$n \in A$$ и f(n) определено. Прообраз множества A при f определяется как множество всех тех n, при которых f(n) определено и принадлежит A.

    Теорема 5. Прообраз и образ перечислимого множества при вычислимой функции перечислимы.

    В самом деле, прообраз перечислимого множества A при вычислимой функции f можно получить так: взять график f, пересечь его с перечислимым множеством N x A и спроектировать на первую координату. Рассуждение для образов аналогично, только координаты меняются местами.

      7. Пусть F перечислимое множество пар натуральных чисел. Докажите. что существует вычислимая функция f, определенная на тех и только тех x, для которых найдется y, при котором $$\langle x,y\rangle\hm\in F$$, причем значение f(x) является одним из таких y. (Это утверждение называют иногда теоремой об униформизации.)

      8. Даны два пересекающихся перечислимых множества X и Y. Докажите, что найдутся непересекающиеся перечислимые множества $$X' \subset X$$ и $$Y' \subset Y$$, для которых $$X' \cup Y' = X \cup Y$$.

      9. Диофантовым называется уравнение, имеющее вид P(x1,...,xn)=0, где P многочлен с целыми коэффициентами. Докажите, что множество диофантовых уравнений, имеющих целые решения, перечислимо. (Оно неразрешимо: в этом состоит известный результат Ю.В.Матиясевича, явившийся решением знаменитой " 10-й проблемы Гильберта".)

      10. Не ссылаясь на доказательство теоремы Ферма, покажите, что множество всех показателей n, для которых существует решение уравнения xn + yn = zn в целых положительных числах, перечислимо. (Как теперь известно, это множество содержит лишь числа 1 и 2.)

      11. Покажите, что всякое бесконечное перечислимое множество можно записать в виде {a(0), a(1), a(2),...}, где a вычислимая функция, все значения которой различны. (Указание: в ходе перечисления удаляем повторения.)

      12. Покажите, что всякое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество. (Указание: воспользуемся предыдущей задачей и выберем возрастающую подпоследовательность.)

      13. Покажите, что для всякой вычислимой функции f существует вычислимая функция, являющаяся " псевдообратной " к f в следующем смысле: область определения g совпадает с областью значений f, и при этом f(g(f(x)))=f(x) для всех x, при которых f(x) определено.

      14. Действительное число $$\alpha$$ называется вычислимым, если существует вычислимая функция a, которая по любому рациональному $$\varepsilon > 0$$ дает рациональное приближение к $$\alpha$$ с ошибкой не более $$\varepsilon,$$ т.е. $$|\alpha - a(\varepsilon )| <= \varepsilon$$ для любого рационального $$\varepsilon > 0$$. (Рациональное число является конструктивным объектом, так что понятие вычислимости не требует специального уточнения.)

  • Докажите, что число $$\alpha$$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $$\alpha,$$ разрешимо.
  • Докажите, что число $$\alpha$$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима.
  • Докажите, что число $$\alpha$$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $$\alpha$$ (последнее означает, что можно алгоритмически указать N по $$\varepsilon$$ в стандартном $$\varepsilon$$ - N -определении сходимости.)
  • Покажите, что сумма, произведение, разность и частное вычислимых действительных чисел вычислимы. Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
  • Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых действительных чисел вычислим.
  • Действительное число $$\alpha$$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $$\alpha,$$ перечислимо. (Перечислимость сверху определяется аналогично.) Докажите, что число $$\alpha$$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
  • Докажите, что действительное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
    •

    Дальнейшие свойства вычислимых действительных чисел см. в задаче 23.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^