Введение

Реальное число, которое может быть вычислено с произвольной точностью.

В математике вычислимые числа — это реальные числа, которые могут быть вычислены с любой требуемой точностью с помощью конечного, завершающегося алгоритма. Они также известны как рекурсивные числа, эффективные числа или вычислимые действительные числа, или рекурсивные действительные числа. Концепция вычислимого действительного числа была введена Эмилем Борелем в 1912 году, используя интуитивное представление о вычислимости, доступное в то время. Эквивалентные определения могут быть даны с использованием μ-рекурсивных функций, машин Тьюринга или λ-исчисления в качестве формального представления алгоритмов. Вычислимые числа образуют действительное замкнутое поле и могут использоваться вместо действительных чисел для многих, но не всех, математических целей.

Неформальное определение с использованием машины Тьюринга в качестве примера

В дальнейшем Марвин Минский определяет вычисляемые числа аналогично определению Алана Тьюринга 1936 года, то есть как «последовательности цифр, интерпретируемые как десятичные дроби» между 0 и 1:

text=Вычислимое число – это число, для которого существует машина Тьюринга, которая, получив n на своей начальной ленте, завершает работу, выведя n-ю цифру этого числа [закодированную на ленте]. Ключевые моменты в определении: (1) некоторое n задается в начале, (2) для любого n вычисление занимает лишь конечное число шагов, после чего машина выдает требуемый результат и останавливается. Альтернативная формулировка (2) – машина последовательно выводит на ленту все n цифр, останавливаясь после вывода n-й – подчеркивает наблюдение Минского: (3) с помощью машины Тьюринга конечное определение – в виде таблицы состояний машины – используется для определения потенциально бесконечной последовательности десятичных цифр. Однако это не современное определение, которое требует лишь точности результата в пределах заданной погрешности. Вышеприведенное неформальное определение подвержено проблеме округления, известной как дилемма составителя таблиц, в то время как современное определение – нет.

Не поддается вычислению

Присвоение числа Гёделя каждому определению машины Тьюринга порождает подмножество натуральных чисел, соответствующих вычислимым числам, и определяет сюръекцию из множества чисел Гёделя на множество вычислимых чисел. Существует лишь счетное количество машин Тьюринга, что показывает, что вычислимые числа счетны. Однако множество этих чисел Гёделя не является вычислимо перечислимым (и, следовательно, не являются и подмножества этого множества, определяемые через него). Это связано с тем, что не существует алгоритма, позволяющего определить, каким числам Гёделя соответствуют машины Тьюринга, порождающие вычислимые действительные числа. Для порождения вычислимого действительного числа машина Тьюринга должна вычислять тотальную функцию, но соответствующая задача о разрешимости имеет степень Тьюринга 0′′. Следовательно, не существует сюръективной вычислимой функции из натуральных чисел на множество машин, представляющих вычислимые действительные числа, и диагональный аргумент Кантора нельзя конструктивно использовать для демонстрации их несчётности. Хотя множество действительных чисел несчётно, множество вычислимых чисел классически счетно, и, следовательно, почти все действительные числа невычислимы. Здесь, для любого заданного вычислимого числа, принцип благоупорядоченности гарантирует существование минимального элемента в множестве, соответствующего этому числу, и, следовательно, существует подмножество, состоящее из минимальных элементов, на котором отображение является биекцией. Обратное к этой биекции является инъекцией из множества вычислимых чисел в натуральные числа, доказывающей их счетность. Но, повторимся, это подмножество не вычислимо, даже несмотря на то, что сами вычислимые действительные числа упорядочены.

Свойства как поле

Арифметические операции над вычислимыми числами сами по себе вычислимы в том смысле, что если действительные числа a и b вычислимы, то вычислимы и следующие действительные числа: a + b, a – b, ab и a / b, при условии, что b не равно нулю. Эти операции, на самом деле, равномерно вычислимы; например, существует машина Тьюринга, которая на входе (A, B) выдает результат r, где A – это описание машины Тьюринга, аппроксимирующей a, B – это описание машины Тьюринга, аппроксимирующей b, а r – это аппроксимация a + b. Тот факт, что вычислимые действительные числа образуют поле, был впервые доказан Генри Гордоном Райсом в 1954 году. Однако вычислимые действительные числа не образуют вычислимое поле, поскольку определение вычислимого поля требует эффективного равенства.

Невычислимость заказа

Отношение порядка на вычислимых числах не является вычислимым. Пусть A – описание машины Тьюринга, аппроксимирующей число. Тогда не существует машины Тьюринга, которая на входе A выдает "ДА", если , и "НЕТ", если . Чтобы понять, почему, предположим, что машина, описанная A, продолжает выдавать 0 в качестве приближений. Неясно, сколько времени нужно ждать, прежде чем решить, что машина никогда не выдаст приближение, которое заставит a стать положительным. Таким образом, машине в конечном итоге придется угадать, что число равно 0, чтобы выдать результат; последовательность может впоследствии отличаться от 0. Эту идею можно использовать для доказательства того, что машина ошибается на некоторых последовательностях, если она вычисляет полную функцию. Аналогичная проблема возникает при представлении вычислимых действительных чисел в виде сечений Дедекинда. То же самое справедливо и для отношения равенства: проверка на равенство не является вычислимой. Хотя полное отношение порядка не вычислимо, его ограничение парами неравных чисел вычислимо. То есть существует программа, которая принимает на вход две машины Тьюринга A и B, аппроксимирующие числа и , где , и выдает, если , или . Достаточно использовать аппроксимации, где , поэтому, последовательно уменьшая (приближаясь к 0), в конечном итоге можно определить, верно ли , или .

Другие свойства

Вычислимые действительные числа не обладают всеми свойствами действительных чисел, используемых в математическом анализе. Например, наименьшая верхняя граница ограниченной возрастающей вычислимой последовательности вычислимых действительных чисел не обязана быть вычислимым действительным числом. Последовательность, обладающая этим свойством, называется последовательностью Спекера, поскольку первое построение принадлежит Эрнсту Спекеру (1949 год). Несмотря на существование подобных контрпримеров, некоторые разделы математического анализа и вещественного анализа могут быть развиты в области вычислимых чисел, что приводит к изучению вычислимого анализа. Каждое вычислимое число арифметически определимо, но не наоборот. Существует множество арифметически определенных, но невычислимых действительных чисел, в том числе любое число, кодирующее решение проблемы останова (или любой другой неразрешимой проблемы) согласно выбранной схеме кодирования. Постоянная Чейтина, Ω, является одним из типов действительных чисел, Тьюринг-эквивалентным проблеме останова. Оба этих примера фактически определяют бесконечное множество определяемых, невычислимых чисел – по одному для каждой универсальной машины Тьюринга. Действительное число вычислимо тогда и только тогда, когда множество натуральных чисел, которое оно представляет (при записи в двоичной системе счисления и рассмотрении как характеристической функции), является вычислимым. Множество вычислимых действительных чисел (а также любое счетное, плотно упорядоченное подмножество вычислимых действительных чисел без концов) порядково изоморфно множеству рациональных чисел.

Использование вместо реалов

Считаемые числа включают в себя конкретные действительные числа, которые встречаются на практике, включая все действительные алгебраические числа, а также числа e, π и многие другие трансцендентные числа. Хотя вычислимые действительные числа охватывают те действительные числа, которые мы можем вычислить или приближенно оценить, предположение о том, что все действительные числа вычислимы, приводит к существенно иным выводам относительно действительных чисел. Естественно возникает вопрос о том, возможно ли отказаться от полного множества действительных чисел и использовать вычислимые числа во всей математике. Эта идея привлекательна с точки зрения конструктивизма и была развита тем, что Эрретт Бишоп и Фред Ричман называют русской школой конструктивной математики. Для построения анализа над вычислимыми числами необходимо соблюдать определенную осторожность. Например, при использовании классического определения последовательности множество вычислимых чисел не является замкнутым относительно базовой операции взятия супремума ограниченной последовательности (например, рассмотрим последовательность Спекера, см. раздел выше). Эта трудность преодолевается путем рассмотрения только тех последовательностей, которые имеют вычислимый модуль сходимости. Получающаяся математическая теория называется вычислимым анализом.

Реализация точных арифметических вычислений

Компьютерные пакеты, представляющие вещественные числа в виде программ, вычисляющих приближения, были предложены еще в 1985 году под названием "точная арифметика". Современные примеры включают библиотеку CoRN (Coq) и пакет RealLib (C++). Смежное направление исследований основано на взятии программы, работающей как с вещественными числами, и выполнении её с рациональными или числами с плавающей точкой достаточной точности, например, пакет.