Парадокс Ришара

С помощью некоторых фраз какого-либо языка могут быть охарактеризованы те или иные вещественные числа. Например, фраза «отношение длины окружности к длине её диаметра» характеризует число «пи», а фраза «две целых и три десятых» характеризует число 2,3. Все такие фразы этого языка можно пронумеровать определённым способом (например, если упорядочить фразы по алфавиту как в словаре, то каждая фраза получит тот номер, на каком месте она находится). Теперь оставим в этой нумерации фраз только те фразы, которые характеризуют одно вещественное число (а не два и более). Число, которое охарактеризовано при такой нумерации фразой номер n, назовем n-м числом Ришара.

Рассмотрим такую фразу: «Вещественное число, у которого n-й десятичный знак равен 1, если у n-го числа Ришара n-й десятичный знак не равен 1, и n-й десятичный знак равен 2, если у n-го числа Ришара n-й десятичный знак равен 1». Эта фраза определяет некоторое число Ришара, допустим, k-е; однако, согласно определению, оно отличается от k-го числа Ришара в k-м десятичном знаке. Таким образом, пришли к противоречию.

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

Например, точное значение «две целых и три десятых» вычислимо, поскольку результат вычислений есть рациональное число, которое можно записать отношением натуральных чисел за конечное время, используя конечный объем памяти. А точное значение «отношение длины окружности к длине её диаметра» невычислимо в принципе, поскольку искомый результат на самом деле является иррациональным числом, точное значение которого даже теоретически невозможно представить никаким отношением натуральных чисел, какие бы числа мы ни пытались подбирать. За конечное время можно вычислить лишь приближенное значение числа Пи с любым конечным количеством цифр после запятой, на вычисление которых хватит времени, и на хранение которых хватит памяти (т.е. вычислимым является лишь приближенное значение числа Пи в виде рационального числа). Но точное значение числа Пи невычислимо: любая программа по вычислению точного значения числа Пи будет работать бесконечно долго и потребует бесконечного объёма памяти для хранения все большего числа данных, накапливаемых с каждой итерацией. Условие записать "отношение длины окружности к длине её диаметра" натуральными числами невыполнимо в принципе, если не оговорена допустимая погрешность.

Аналогично при вычислении некоего «числа Ришара» потребуется выполнить проверку приведённого условия «Вещественное число, у которого n-й десятичный знак равен 1, если у n-го числа Ришара n-й десятичный знак не равен 1, и n-й десятичный знак равен 2, если у n-го числа Ришара n-й десятичный знак равен 1». Такая проверка потребует выполнения программы с рекурсивным вызовом самой себя (в описании присутствуют операции над неким "числа Ришара", для вычисления значения которого необходимо снова начать очередное выполнение алгоритма этой программы с рекурсивным погружением без ограничения глубины вложенности с расчётом на использование бесконечно большого объёма памяти и неограниченного времени).

Искомое «число Ришара» в приведенной формулировке невычислимо и алгоритмически неразрешимо, т.е. не существует никакого алгоритма, способного вычислить его за конечное время по той простой причине, что условие правильного результата заведомо невыполнимо.

• Мендельсон Эллиот. Введение в математическую логику. — М.: «Наука», 1971. — 320 с.

• Парадокс Берри