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

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

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

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

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

Неформальное определение на примере машины Тьюринга

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Характеристики

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

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

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

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

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

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

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

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

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

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

Другие объекты недвижимости

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

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

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

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

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

Цифровые строки и пространства Кантора и Бэра

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

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

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

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

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

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

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

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

Используйте вместо действительных чисел

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

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

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

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

Смотрите также

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

Примечания

1. ван дер Хувен (2006).
2. П. Одифредди, Классическая теория рекурсии (1989), стр.8. Северная Голландия, 0-444-87295-7
3. Тьюринг (1936).
4. Минский (1967).
5. Райс (1954).
6. Бриджес и Ричман (1987), с. 58.
7. Спеккер (1949).
8. Херст (2007).
9. Залта, Эдвард Н., изд. (2022), «Русская школа конструктивной математики», Конструктивная математика , Исследовательская лаборатория метафизики, Стэнфордский университет
10. Бем, Ханс-Дж.; Картрайт, Роберт; Риггл, Марк; О'Доннелл, Майкл Дж. (8 августа 1986 г.). «Точная действительная арифметика: пример программирования высшего порядка» (PDF) . Материалы конференции ACM 1986 года по LISP и функциональному программированию - LFP '86 . стр. 162–173. дои : 10.1145/319838.319860. ISBN 0897912004. S2CID  12934546. Архивировано (PDF) из оригинала 24 сентября 2020 г.
11. О'Коннор, Рассел (2008). «Сертифицированное точное вычисление трансцендентных действительных чисел в Coq». Доказательство теорем в логике высшего порядка . Конспекты лекций по информатике. Том. 5170. стр. 246–261. arXiv : 0805.2438 . дои : 10.1007/978-3-540-71067-7_21. ISBN 978-3-540-71065-3. S2CID  17959745.
12. Ламбов (2015).
13. Гоуленд, Пол; Лестер, Дэвид (2001). «Обзор реализаций точной арифметики» (PDF) . Вычислимость и сложность анализа . Конспекты лекций по информатике. Том. 2064. Спрингер. стр. 30–47. дои : 10.1007/3-540-45335-0_3. ISBN 978-3-540-42197-9. Архивировано (PDF) из оригинала 24 марта 2022 г.

Рекомендации

• Бриджес, Дуглас; Ричман, Фред (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. ОКЛК  0131655639.
• Райс, Генри Гордон (1954). «Рекурсивные действительные числа». Труды Американского математического общества . 5 (5): 784–791. дои : 10.1090/S0002-9939-1954-0063328-5 . JSTOR  2031867.
• Спекер, Э. (1949). «Nicht konstruktiv beweisbare Sätze der Analysis» (PDF) . Журнал символической логики . 14 (3): 145–158. дои : 10.2307/2267043. JSTOR  2267043. S2CID  11382421. Архивировано (PDF) из оригинала 21 июля 2018 г.
• Тьюринг, AM (1936). «О вычислимых числах с применением к проблеме Entscheidungs». Труды Лондонского математического общества . Серия 2 (издана в 1937 г.). 42 (1): 230–65. дои : 10.1112/plms/s2-42.1.230. S2CID  73712.
  Тьюринг, AM (1938). «О вычислимых числах с применением к проблеме Entscheidungs: исправление». Труды Лондонского математического общества . Серия 2 (издана в 1937 г.). 43 (6): 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). Простое введение в вычислительный анализ. Фернунив., Факберайх Информатик.