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

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

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

F = {(х, у) | f(x) определено и равно у}

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

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

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

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

Пусть / — частичная функция с натуральными аргу­ментами и значениями. Образ множества А при / опреде­ляется как множество всех чисел f(n), для которых п £ А и f(n) определено. Прообраз множества А при / опреде­ляется как множество всех тех п, при которых f(n) опре­делено и принадлежит А.

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

<] В самом деле, прообраз перечислимого множе­ства А при вычислимой функции / можно получить так: взять график /, пересечь его с перечислимым множе­ством N х А и спроектировать на первую координату. Рассуждение для образов аналогично, только координа­ты меняются местами. >

7. Пусть /' — перечислимое множество нар натуральных чисел. Докажите, что существует вычислимая функция /, определённая на тех и только тех х, для которых найдётся у, при котором (з;, у) £ Ь\ причём значение ]'(з;) является одним из таких у. (Это утверждение называют иногда теоремой об униформизации.)

8. Даны два пересекающихся перечислимых множества X и У. Докажите, что найдутся непересекающиеся перечисли­мые множества X' С X и У' С У, для которых Х'иУ' = ХиУ.

9. Диофантовым называется уравнение, имеющее вид Р(з;\, . . . ,з;„) = О, где Р — многочлен с целыми коэффици­ентами. Докажите, что множество диофантовых уравнений, имеющих целые решения, перечислимо. (Оно неразрешимо: в этом состоит известный результат Ю. В. Матиясевича, явив­шийся решением знаменитой «10-й проблемы Гильберта».)

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

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

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

13. Покажите, что для всякой вычислимой функции / существует вычислимая функция, являющаяся «исевдообрат-ной» к / в следующем смысле: область определения д совпа­дает с областью значений /, и при этом (з;))) = ]'(з;) для всех з;, при которых ]'(з;) определено.

14. Действительное число а называется вычислимым, если существует вычислимая функция а, которая но любому раци­ональному е > 0 даёт рациональное приближение к а с ошиб­кой не более е, т.е. \а — а(е)| ^ е для любого рационального е > 0. (Рациональное число является конструктивным объек­том, так что понятие вычислимости не требует специального уточнения.)

(а) Докажите, что число а вычислимо тогда и только то­гда, когда множество рациональных чисел, меньших а, раз­решимо.

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

(в) Докажите, что число а вычислимо тогда и только то­гда, когда существует вычислимая последовательность рацио­нальных чисел, вычислимо сходящаяся к а (последнее означа­ет, что можно алгоритмически указать N но £ в стандартном £- /^-определении сходимости.)

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

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

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

(ж) Докажите, что действительное число вычислимо то­гда и только тогда, когда оно иеречислимо снизу и сверху.

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