Interested Article - Парадокс Ришара

Парадо́кс Риша́ра — , впервые описанный французским математиком Жюлем Ришаром в 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». Такая проверка потребует выполнения программы с рекурсивным вызовом самой себя (в описании присутствуют операции над неким «числом Ришара», для вычисления значения которого необходимо снова начать очередное выполнение алгоритма этой программы с рекурсивным погружением без ограничения глубины вложенности с расчётом на использование бесконечно большого объёма памяти и неограниченного времени).

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