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

Парадо́кс Риша́ра — семантический парадокс, впервые описанный французским математиком Жюлем Ришаром в 1905 году.

Описание

С помощью некоторых фраз русского языка могут быть охарактеризованы те или иные вещественные числа. Например, фраза «отношение длины окружности к длине её диаметра» характеризует число Пи, а фраза «две целых и три десятых» характеризует число 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 с.

См. также

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