Вычислимое число

Не путать с конструктивным числом .

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

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

Эквивалентные определения могут быть даны с использованием µ-рекурсивных функций , машин Тьюринга или λ-исчисления в качестве формального представления алгоритмов. Вычислимые числа образуют реальное закрытое поле и могут использоваться вместо действительных чисел во многих, но не во всех математических целях.

машины Тьюринга

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

Вычислимое число [является] таким, для которого существует машина Тьюринга, которая, учитывая n на ее начальной ленте, заканчивается n -й цифрой этого числа [закодированной на ее ленте].

Ключевые понятия в определении: (1) некоторое n указано в начале, (2) для любого n вычисление занимает только конечное число шагов, после чего машина выдает желаемый результат и завершает работу.

Альтернативная форма (2) – машина последовательно печатает все n цифр на своей ленте, останавливаясь после печати n -й – подчеркивает наблюдение Мински: (3) Что с использованием машины Тьюринга конечное определение – в форме таблицы состояний машины – используется для определения потенциально бесконечной строки десятичных цифр.

Однако это не современное определение, которое требует только того, чтобы результат был точным в пределах любой заданной точности. Неофициальное определение, приведенное выше, подвержено проблеме округления, называемой дилеммой столовщика, тогда как современное определение - нет.

Формальное определение

Действительное число a вычислимо , если его можно аппроксимировать некоторой вычислимой функцией. $f:\mathbb {N} \to \mathbb {Z}$ следующим образом: по любому положительному целому числу n функция выдает целое число f ( n ), такое что:

${f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}.$

Есть два похожих определения, которые эквивалентны:

• Существует вычислимая функция, которая при любой положительной рациональной ошибке ограничивается $\varepsilon$, производит такое рациональное число r , что $|r-a|\leq \varepsilon .$
• Существует вычислимая последовательность рациональных чисел $q_{i}$ сходящиеся к $a$ такой, что $|q_{i}-q_{i+1}|<2^{-i}\,$ для каждого я .

Существует еще одно эквивалентное определение вычислимых чисел с помощью вычислимых дедекиндовых разрезов . — Вычислимый дедекиндовый разрез это вычислимая функция. $D\;$ который при наличии рационального числа $r$ по мере возврата ввода $D(r)=\mathrm {true} \;$ или $D(r)=\mathrm {false} \;$, удовлетворяющий следующим условиям:

$\exists rD(r)=\mathrm {true} \;$

$\exists rD(r)=\mathrm {false} \;$

$(D(r)=\mathrm {true} )\wedge (D(s)=\mathrm {false} )\Rightarrow r<s\;$

$D(r)=\mathrm {true} \Rightarrow \exists s>r,D(s)=\mathrm {true} .\;$

Примером может служить программа D , определяющая кубический корень из 3. Предполагая, что $q>0\;$ это определяется:

$p^{3}<3q^{3}\Rightarrow D(p/q)=\mathrm {true} \;$

$p^{3}>3q^{3}\Rightarrow D(p/q)=\mathrm {false} .\;$

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

Комплексное число называется вычислимым, если его действительная и мнимая части вычислимы.

Свойства

Не вычислимо перечислимо

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

Хотя множество действительных чисел неисчислимо , множество вычислимых чисел классически счетно , и, следовательно, почти все действительные числа невычислимы. Здесь для любого вычислимого числа $x,$ принцип упорядоченности предполагает наличие минимального элемента в $S$ что соответствует $x$, и поэтому существует подмножество, состоящее из минимальных элементов, на котором отображение является биекцией . Обратная биекция — это инъекция в натуральные числа вычислимых чисел, доказывающая их счётность. Но, опять же, это подмножество не вычислимо, хотя вычислимые числа сами по себе упорядочены.

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

Арифметические операции над вычислимыми числами сами по себе вычислимы в том смысле, что всякий раз, когда действительные числа a и b вычислимы, тогда также вычислимы следующие действительные числа: a + b , a - b , ab и a/b , если b не равно нулю.Эти операции на самом деле равномерно вычислимы ; например, есть машина Тьюринга, которая на входе ( A , B , $\epsilon$) выдает результат r , где A — описание машины Тьюринга, аппроксимирующей a , B — описание машины Тьюринга, аппроксимирующей b , а r — $\epsilon$ аппроксимация a + b .

Тот факт, что вычислимые действительные числа образуют поле, впервые доказал Генри Гордон Райс в 1954 году.

Однако вычислимые числа не образуют вычислимое поле , поскольку определение вычислимого поля требует эффективного равенства.

Невычислимость порядка

Отношение порядка вычислимых чисел не вычислимо. Пусть A — описание машины Тьюринга, аппроксимирующей число $a$. Тогда не существует машины Тьюринга, которая на входе А выдает «ДА», если $a>0$ и «НЕТ», если $a\leq 0.$ Чтобы понять почему, предположим, что машина, описанная А, продолжает выводить 0 как $\epsilon$ приближения. Неясно, сколько времени придется ждать, прежде чем решить, что машина никогда не выдаст приближение, которое заставит a быть положительным. Таким образом, чтобы выдать результат, машине в конечном итоге придется угадать, что число будет равно 0; позже последовательность может стать отличной от 0. Эту идею можно использовать, чтобы показать, что машина ошибается в некоторых последовательностях, если она вычисляет полную функцию. Аналогичная проблема возникает, когда вычислимые действительные числа представляются в виде дедекиндовых разрезов . То же самое справедливо и для отношения равенства: критерий равенства не вычислим.

Хотя отношение полного порядка не вычислимо, его ограничение на пары неравных чисел вычислимо. То есть существует программа, которая принимает на вход две машины Тьюринга A и B, аппроксимирующие числа. $a$ и $b$, где $a\neq b$и выводит ли $a<b$ или $a>b.$ Достаточно использовать $\epsilon$-аппроксимации, где $\epsilon <|b-a|/2,$ поэтому, принимая все более малые $\epsilon$ (приближаясь к 0), в конечном итоге можно решить, является ли $a<b$ или $a>b.$

Другая недвижимость

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

Каждое вычислимое число арифметически определимо , но не наоборот. Существует множество арифметически определимых, невычислимых действительных чисел, в том числе:

• любое число, которое кодирует решение проблемы остановки (или любой другой неразрешимой проблемы ) в соответствии с выбранной схемой кодирования.
• постоянная Чайтина , $\Omega$, который представляет собой тип действительного числа, эквивалентный по Тьюрингу проблеме остановки.

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

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

строки и пространства Кантора

В оригинальной статье Тьюринга вычислимые числа определялись следующим образом:

Действительное число является вычислимым, если его последовательность цифр можно получить с помощью какого-либо алгоритма или машины Тьюринга. Алгоритм принимает целое число $n\geq 1$ в качестве входных данных и производит $n$-я цифра десятичного представления действительного числа в качестве вывода.

(Десятичное расширение a относится только к цифрам, следующим за десятичной запятой.)

Тьюринг знал, что это определение эквивалентно $\epsilon$-определение аппроксимации дано выше. Аргументация ведется следующим образом: если число вычислимо в смысле Тьюринга, то оно также вычислимо в смысле Тьюринга. $\epsilon$ смысл: если $n>\log _{10}(1/\epsilon )$, то первые n цифр десятичного представления a дают $\epsilon$ приближение а . Наоборот, мы выбираем $\epsilon$ вычислимое действительное число a и генерировать все более точные приближения до тех пор, пока не будет определена n -я цифра после запятой. Это всегда генерирует десятичное разложение, равное a , но оно может ошибочно заканчиваться бесконечной последовательностью девяток, и в этом случае оно должно иметь конечное (и, следовательно, вычислимое) правильное десятичное разложение.

Если определенные топологические свойства действительных чисел не имеют значения, часто удобнее иметь дело с элементами $2^{\omega }$ (всего 0,1-значные функции) вместо действительных чисел в $[0,1]$. Члены $2^{\omega }$ можно отождествить с двоично-десятичными разложениями, но поскольку десятичные разложения $.d_{1}d_{2}\ldots d_{n}0111\ldots$ и $.d_{1}d_{2}\ldots d_{n}10$ обозначают одно и то же действительное число, интервал $[0,1]$ может быть только биективно (и гомеоморфно относительно топологии подмножества) отождествлено с подмножеством $2^{\omega }$ не оканчивающееся на все 1.

Обратите внимание, что это свойство десятичных разложений означает, что невозможно эффективно идентифицировать вычислимые действительные числа, определенные в терминах десятичных разложений, и числа, определенные в $\epsilon$ смысл приближения. Херст показал, что не существует алгоритма, который принимал бы в качестве входных данных описание машины Тьюринга, производящей $\epsilon$ аппроксимации вычислимого числа a и выдает на выходе машину Тьюринга, которая перечисляет цифры a в смысле определения Тьюринга. Точно так же это означает, что арифметические операции с вычислимыми числами не эффективны для их десятичных представлений, как при сложении десятичных чисел. Чтобы получить одну цифру, может потребоваться посмотреть сколь угодно далеко вправо, чтобы определить, есть ли перенос в текущее местоположение. Отсутствие единообразия является одной из причин, почему в современном определении вычислимых чисел используются $\epsilon$ приближения, а не десятичные разложения.

Однако с точки зрения теории вычислимости или теории меры эти две структуры $2^{\omega }$ и $[0,1]$ по сути идентичны. Таким образом, теоретики вычислимости часто ссылаются на членов $2^{\omega }$ как настоящие. Пока $2^{\omega }$ , полностью отключен по вопросам о $\Pi _{1}^{0}$ классы или случайность, в которых легче работать $2^{\omega }$.

Элементы $\omega ^{\omega }$ иногда также называются реалиями и хотя содержат гомеоморфный образ $\mathbb {R}$, $\omega ^{\omega }$ даже не является локально компактным (помимо того, что он полностью отключен). Это приводит к реальным различиям в вычислительных свойствах. Например, $x\in \mathbb {R}$ удовлетворяющий $\forall (n\in \omega )\phi (x,n)$, с $\phi (x,n)$ свободный квантор, должен быть вычислимым, а уникальный $x\in \omega ^{\omega }$ удовлетворяющее универсальной формуле, может занимать сколь угодно высокое положение в гиперарифметической иерархии .

Используйте вместо реалов

К вычислимым числам относятся конкретные действительные числа, которые встречаются на практике, включая все действительные алгебраические числа , а также e , π и многие другие трансцендентные числа . Хотя вычислимые действительные числа исчерпывают те действительные числа, которые мы можем вычислить или аппроксимировать, предположение о том, что все действительные числа вычислимы, приводит к существенно различным выводам о действительных числах. Естественно возникает вопрос, можно ли распорядиться полным набором действительных чисел и использовать вычислимые числа для всей математики. Эта идея привлекательна с конструктивистской точки зрения и поддерживается русской школой конструктивной математики.

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

Реализации точной арифметики

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

См. также

• Конструктивный номер
• Определяемое число
• Полувычислимая функция
• Трансвычислительная проблема

Ссылки

• Бриджес, Дуглас; Ричман, Фред (1987). Разновидности конструктивной математики . Издательство Кембриджского университета. ISBN  978-0-521-31802-0 .
• Херст, Джеффри Л. (2007). «Представления действительных чисел в обратной математике» . Вестник Польской академии наук, Математика . 55 (4): 303–316. дои : 10.4064/ba55-4-2 .
• Ламбов, Бранимир (5 апреля 2015 г.). «РеалЛиб» . Гитхаб.
• Мински, Марвин (1967). «9. Вычислимые действительные числа». Вычисления: конечные и бесконечные машины . Прентис-Холл. ISBN  0-13-165563-9 . OCLC   0131655639 .
• Райс, Генри Гордон (1954). «Рекурсивные действительные числа» . Труды Американского математического общества . 5 (5): 784–791. дои : 10.1090/S0002-9939-1954-0063328-5 . JSTOR   2031867 .
• Спекер, Э. (1949). «Неконструктивно доказуемые теоремы анализа» (PDF) . Журнал символической логики . 14 (3): 145–158. дои : 10.2307/2267043 . JSTOR   2267043 . S2CID   11382421 . Архивировано (PDF) из оригинала 21 июля 2018 г.
• Тьюринг, AM (1936). «О вычислимых числах с применением к проблеме Entscheidungs». Труды Лондонского математического общества . Серия 2. 42 (1) (опубликовано в 1937 г.): 230–65. дои : 10.1112/plms/s2-42.1.230 . S2CID   73712 .
  Тьюринг, AM (1938). «О вычислимых числах с применением к проблеме Entscheidungs: исправление» . Труды Лондонского математического общества . Серия 2. 43 (6) (опубликовано в 1937 г.): 544–6. дои : 10.1112/plms/s2-43.6.544 . В этой статье были представлены вычислимые числа (и а-машины Тьюринга); определение вычислимых чисел использует бесконечные десятичные последовательности.
• ван дер Хувен, Йорис (2006). «Вычисления с эффективными действительными числами» . Теоретическая информатика . 351 (1): 52–60. дои : 10.1016/j.tcs.2005.09.060 .

Дальнейшее чтение

• Аберт, Оливер (1968). «Анализ в поле вычислимых чисел» . Журнал Ассоциации вычислительной техники . 15 (2): 276–299. дои : 10.1145/321450.321460 . S2CID   18135005 . В этой статье описывается развитие исчисления над полем вычислимых чисел.
• Епископ, Спасение; Бриджес, Дуглас (1985). Конструктивный анализ . Спрингер. ISBN  0-387-15066-8 .
• Столтенберг-Хансен, В.; Такер, СП (1999). «Вычислимые кольца и поля» . В Гриффоре, ER (ред.). Справочник по теории вычислимости . Эльзевир. стр. 363–448. ISBN  978-0-08-053304-9 .
• Вайраух, Клаус (2000). Вычислительный анализ . Тексты по теоретической информатике. Спрингер. ISBN  3-540-66817-9 . В §1.3.2 вводится определение с помощью вложенных последовательностей интервалов, сходящихся к одноточечному вещественному числу. Другие представления обсуждаются в §4.1.
• Вайраух, Клаус (1995). Простое введение в вычислительный анализ . Фернунов, кафедра компьютерных наук.