Универсальные функции и неразрешимость

Разбить на страницы

Показывать лекцию целиком

Универсальные функции

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

Говорят, что функция U двух натуральных аргументов является универсальной для класса вычислимых функций одного аргумента, если для каждого n функция

$$U_n\colon x \mapsto U(n,x)$$

("сечение" функции U при фиксированном n ) является вычислимой и если все вычислимые функции (одного аргумента) встречаются среди U_n. (Напомним, что ни функция U, ни вычислимые функции одного аргумента не обязаны быть всюду определенными.)

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

Ключевую роль в этом разделе играет такой факт:

Теорема 6.Существует вычислимая функция двух аргументов, являющаяся универсальной функцией для класса вычислимых функций одного аргумента.

Запишем все программы, вычисляющие функции одного аргумента, в вычислимую последовательность p₀, p₁, ... (например, в порядке возрастания их длины). Положим U(i,x) равным результату работы i -ой программы на входе x. Тогда функция U и будет искомой вычислимой универсальной функцией. Сечение U_i будет вычислимой функцией, вычисляемой программой p_i. Алгоритм, вычисляющий саму функцию U, есть по существу интерпретатор для используемого языка программирования (он применяет первый аргумент ко второму, если отождествить программу и ее номер).

15. Все сечения U_n некоторой функции U двух аргументов вычислимы. Следует ли отсюда, что функция U вычислима?

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

Для множеств используется аналогичная терминология: множество $$W \subset N x N$$ называют универсальны для некоторого класса множеств натуральных чисел, если все сечения

$$W_n=\{x\mid \langle n,x\rangle \in W\}$$

множества W принадлежат этому классу и других множеств в классе нет.

Теорема 7.Существует перечислимое множество пар натуральных чисел, универсальное для класса всех перечислимых множеств натуральных чисел.

Рассмотрим область определения универсальной функции U. Она будет универсальным перечислимым множеством, поскольку всякое перечислимое множество является областью определения некоторой вычислимой функции U_n.

17. Как построить универсальное множество, исходя из того, что всякое перечислимое множество есть множество значений некоторой функции U_n?

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

Диагональная конструкция

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

Теорема 8.Не существует вычислимой всюду определенной функции двух аргументов, универсальной для класса всех вычислимых всюду определенных функций одного аргумента.

Воспользуемся "диагональной конструкцией" точно так же доказывается несчетность множества всех бесконечных десятичных дробей. Пусть U произвольная вычислимая всюду определенная функция двух аргументов. Рассмотрим диагональную функцию u(n) = U(n,n). Очевидно, на аргументе n функция u совпадает с функцией U_n, а функция d(n) = u(n) + 1 отличается от U_n. Таким образом, вычислимая всюду определенная функция d(n) отличается от всех сечений U_n, и потому функция U не является универсальной.

Почему это рассуждение не проходит для класса всех вычислимых функций (в том числе частичных)? Дело в том, что значение d(n) = U(n,n) + 1 теперь не обязано отличаться от значения U_n(n) = U(n,n), так как оба они могут быть не определены.

Тем не менее, часть рассуждения остается в силе.

Теорема 9.Существует вычислимая функция d (с натуральными аргументами и значениями), от которой никакая вычислимая функция f не может всюду отличаться: для любой вычислимой функции f найдется такое число n, что f(n) = d(n) (последнее равенство понимается в том смысле, что либо оба значения f(n) и d(n) не определены, либо оба определены и равны).

По существу все уже сказано: такова диагональная функция d(n) = U(n,n) (здесь U вычислимая функция двух аргументов, универсальная для класса вычислимых функций одного аргумента). Любая вычислимая функция f есть U_n при некотором n и потому f(n) = U_n(n) = U(n,n) = d(n).

Теорема 10.Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения.

Такова, например, функция d'(n) = d(n) + 1, где d функция из предыдущей теоремы. В самом деле, любое ее всюду определенное продолжение всюду отличается от d (в тех местах, где функция d определена, функция d' на единицу больше d и потому любое продолжение функции d' отличается от d ; там, где d не определена, любая всюду определенная функция отличается от d ).

19. Докажите, что и сама функция d из доказательства предыдущей теоремы не имеет вычислимого всюду определенного продолжения.

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

Теперь мы можем доказать обещанное утверждение.

Теорема 11.Существует перечислимое неразрешимое множество. (Переформулировка: существует перечислимое множество с неперечислимым дополнением.)

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

$$$$ g(x)=\left\{ \begin{aligned} f(x), \text{ если $x\in F$},\\ 0, \text{ если $x\notin F$} \end{aligned} \right. $$$$

была бы вычислимым всюду определенным продолжением функции f (при вычислении g(x) мы сначала проверяем, лежит ли x в F, если лежит, то вычисляем f(x) ).

Полезно проследить, какое именно множество в итоге оказалось перечислимым и неразрешимым. Легко понять, что это множество тех n, при которых U(n,n) определено. Если вспомнить конструкцию функции U, то это множество тех n, при которых n -я программа останавливается на n. Поэтому иногда говорят, что " проблема самоприменимости " (применимости программы к своему номеру) неразрешима.

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

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

20. Пусть U перечислимое множество пар натуральных чисел, универсальное для класса всех перечислимых множеств натуральных чисел. Докажите, что его " диагональное сечение " $$K\hm=\{x\mid \langle x,x\rangle \hm\in U\}$$ является перечислимым неразрешимым множеством.

21. Некоторое множество S натуральных чисел разрешимо. Разложим все числа из S на простые множители и составим множество D всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество D разрешимо?

22. Множество $$U \subset N x N$$ разрешимо. Можно ли утверждать, что множество " нижних точек " множества U, то есть множество

$$V=\{ \langle x,y\rangle\mid \text{ ($\langle x,y\rangle \in U$) и ($\langle x,z\rangle\notin U$ для всех $z<y$)}\}$$

является разрешимым? Можно ли утверждать, что V перечислимо, если U перечислимо?

23. Покажите, что существуют перечислимые снизу, но не вычислимые числа в смысле определений, данных на с. (Указание. Рассмотрим сумму ряда $$\sum 2^{-k}$$ по всем k из какого-либо перечислимого множества P. Она всегда перечислима снизу, но будет вычислимой только при разрешимом P.)

Мы вернемся к вычислимым действительным числам в задачах 31 и 61.

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

Небольшая модификация рассуждения позволяет доказать усиление доказанной выше теоремы:

Теорема 12.Существует вычислимая функция, принимающая только значения 0 и 1 и не имеющая всюду определенного вычислимого продолжения.

Вместо функции d'(x) = d(x) + 1 можно рассмотреть функцию

$$d''(x)=\left\{ \begin{aligned} 1, \text{ если d(x)=0},\\ 0, \text{ если d(x)>0}\\ \end{aligned} \right.$$

(имеется в виду, что d''(x) не определено, если d(x) не определено). Тогда любое всюду определенное продолжение функции d'' будет по-прежнему отличаться от d всюду и потому не будет вычислимым.

Этот результат можно перевести на язык перечислимых множеств. Говорят, что два непересекающихся множества X и Y отделяются множеством C, если множество C содержит одно из них и не пересекается с другим.

Теорема 13.Существуют два непересекающихся перечислимых множества X и Y, которые не отделяются никаким разрешимым множеством.

В самом деле, пусть d вычислимая функция, принимающая только значения 0 и 1 и не имеющая всюду определенного вычислимого продолжения. Пусть X = {x | d(x) = 1} и Y = {x | d(x) = 0}. Легко видеть, что множества X и Y перечислимы. Пусть они отделяются разрешимым множеством C ; будем считать, что C содержит X и не пересекается c Y (если наоборот, перейдем к дополнению). Тогда характеристическая функция множества C (равная 1 внутри C и 0 вне него) продолжает d.

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

24. Как описать построенные перечислимые неотделимые множества в терминах универсальной функции U(n,x)?

25. Покажите, что существует счетное число непересекающихся перечислимых множеств, никакие два из которых нельзя отделить разрешимым множеством.

Простые множества: конструкция Поста

Существуют и другие конструкции перечислимых неразрешимых множеств. Вот одна из них (предложенная Э.Постом).

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

Теорема 14.Существует простое множество.

Нам нужно, чтобы перечислимое множество S имело иммунное дополнение. Это означает, что S должно пересекаться с любым бесконечным перечислимым множеством. Чтобы гарантировать это, полезно для каждого перечислимого множества V добавить какой-то его элемент в S (хотя бы для бесконечных V ). При этом надо позаботиться о том, чтобы вне S осталось бесконечно много элементов. Это можно гарантировать, если добавлять достаточно большие элементы (например, из множества номер i добавлять только один элемент, притом больший 2i ).

Объясним конструкцию подробнее. Пусть W универсальное перечислимое множество пар, среди сечений W_i которого встречаются все перечислимые множества натуральных чисел. Будем называть W_i " перечислимым множеством номер i " (при этом разным номерам может соответствовать одно и то же множество). Рассмотрим множество пар $$T\hm=\{\langle i,x\rangle \mid (x \hm\in W_i) \text{ и } (x \hm> 2i)\}$$. Это множество перечислимо (как пересечение W и разрешимого множества $$\{\langle i,x\rangle\mid x\hm>2i\}$$ ). Перечисляя его, будем отбрасывать пары, у которых первый член уже встречался ранее. Останется некоторое перечислимое подмножество $$T' \subset T$$. Рассмотрим теперь перечислимое множество S вторых членов пар, входящих в T'.

Это множество пересекается с любым бесконечным перечислимым множеством. В самом деле, если W_i бесконечно, то оно содержит и числа, большие 2i, поэтому в T (а, значит, и в T' ) есть пары с первым членом i. Второй член такой пары из T' будет лежать и в S, и в W_i.

С другой стороны, множество S имеет бесконечное дополнение, поскольку среди чисел от 0 до 2n - 1 максимум n различных чисел могут принадлежать S (это числа, попавшие в S c одной из первых n вертикалей все остальные будут уже больше 2n ).

26. Докажите, что бесконечное множество, не содержащее бесконечных разрешимых подмножеств, иммунно.

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

Страницы: