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

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

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

В математике, вычислимые числа - это действительные числа, которые могут быть вычислены с любой желаемой точностью конечным завершающим алгоритмом . Они также известны как рекурсивные числа, эффективные числа (vanDerHoeven) или вычислимые числа или рекурсивные числа .

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

• 1 Неформальное определение на примере машины Тьюринга
• 2 Формальное определение
• 3 Свойства
  • 3.1 Невычислимо перечислимое
  • 3.2 Свойства как поле
  • 3.3 Невычислимость порядок
  • 3.4 Другие свойства
• 4 Цифры и пространства Кантора и Бэра
• 5 Можно ли использовать вычисляемые числа вместо вещественных чисел?
• 6 Реализация
• 7 См. также
• 8 Ссылки

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

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

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

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

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

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

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

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

• Существует вычислимая функция, которая с учетом любой положительной рациональной границы ошибки $\epsilon \; \{\backslash \; displaystyle\; \backslash \; varepsilon\}$дает рациональное число r такое, что $|\; г\; -\; а\; |\; \le \; \epsilon .\; \{\backslash \; displaystyle\; |\; ra\; |\; \backslash \; leq\; \backslash \; varepsilon.\}$
• Существует вычислимая последовательность рациональных чисел $qi\; \{\backslash \; displaystyle\; q\_\; \{i\}\}$, сходящаяся к $a\; \{\backslash \; displaystyle\; a\}$такой, что для каждого i.

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

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

$\exists \; р\; D\; (r)\; =\; ложь\; \{\backslash \; displaystyle\; \backslash \; exists\; rD\; (r)\; =\; \backslash \; mathrm\; \{false\}\; \backslash ;\}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хотя отношение полного порядка не вычислимо, его ограничение парами неравных чисел вычислимо. То есть есть программа, которая принимает на входе две машины Тьюринга A и B, аппроксимирующие числа a и b, где a ≠ b, и выводит, или $a>b.\; \{\backslash \; displaystyle\; a>b.\}$Достаточно использовать ε-приближения, где поэтому, взяв все меньшее ε (приближающееся к 0), можно в конечном итоге решить, или $a>b.\; \{\backslash \; displaystyle\; a>b.\}$

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

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

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

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

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

Каждое вычислимое число является арифметическим.

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

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

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

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

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

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

Обратите внимание, что это свойство десятичных разложений означает, что невозможно эффективно идентифицировать вычислимые действительные числа, определенные в терминах десятичного разложения, и те, которые определены в $ϵ\; \{\backslash \; displaystyle\; \backslash \; epsilon\}$смысл приближения. Херст показал, что не существует алгоритма, который принимает в качестве входных данных описание машины Тьюринга, которая производит $ϵ\; \{\backslash \; displaystyle\; \backslash \; epsilon\}$приближения для вычислимого числа a, а на выходе создает машину Тьюринга, которая перечисляет цифры a в смысле определения Тьюринга (см. Hirst 2007). Точно так же это означает, что арифметические операции с вычислимыми действительными числами не эффективны для их десятичных представлений, так как при сложении десятичных чисел для получения одной цифры может потребоваться сколь угодно далеко вправо, чтобы определить, есть ли перенос на Текущее местоположение. Это отсутствие единообразия - одна из причин того, что современное определение вычислимых чисел использует $ϵ\; \{\backslash \; displaystyle\; \backslash \; epsilon\}$приближения, а не десятичные разложения.

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

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

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

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

. Существуют некоторые компьютерные пакеты, которые работают с вычислимыми действительными числами, представляя действительные числа как программы, вычисляющие приближения. Одним из примеров является пакет RealLib Lambov (2015).

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