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

В этой статье есть встроенные цитаты , но они не отформатированы должным образом . Пожалуйста, улучшите эту статью, исправив их . Ссылки в скобках устарели ; преобразовать в сокращенные сноски . ( Сентябрь 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

В математике , вычисляемые числа являются действительными числами , которые могут быть вычислены с точностью до любой желаемой точности конечного, согласующих алгоритм . Они также известны как рекурсивные числа , эффективные числа (vanDerHoeven) или вычислимые действительные числа или рекурсивные числа . ^{[ необходима цитата ]}

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

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

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

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

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

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

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

Формальное определение [ править ]

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

${\ Displaystyle {е (п) -1 \ над n} \ leq a \ leq {f (n) +1 \ над n}.}$

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

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

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

${\ Displaystyle \ существует rD (r) = \ mathrm {true} \;}$

${\ Displaystyle \ существует 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 уникальна для каждого вычислимого числа (хотя, конечно, две разные программы могут предоставлять одну и ту же функцию).

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

Свойства [ править ]

Невозможно перечислить [ править ]

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

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

Свойства как поле [ править ]

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

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

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

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

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

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

Другие свойства [ править ]

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

Каждое вычислимое число определимо , но не наоборот. Есть много определяемых, невычислимых действительных чисел, в том числе:

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

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

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

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

Строки цифр и пространства Кантора и Бэра [ править ]

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

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

(Расширение десятичной из относится только к цифрам после десятичной точки.)

Тьюринг знал, что это определение эквивалентно определению -апроксимации, данному выше. Аргумент продолжается следующим образом: если число вычислимо в смысле Тьюринга, то оно также вычислимо в смысле: если , то первые n цифр десятичного разложения для a обеспечивают приближение к a . Наоборот, мы выбираем вычислимое действительное число a и генерируем все более точные приближения до тех пор, пока n- я цифра после десятичной точки не станет точной . Это всегда порождает разложение десятичного равное а${\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 }}$

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

Однако с точки зрения вычислений или теории меры эти две структуры и по существу идентичны, и теоретики вычислимости часто называют их члены действительными. Хотя он полностью отключен , для вопросов о классах или случайности работать с ним гораздо проще .${\displaystyle 2^{\omega }}$${\displaystyle [0,1]}$${\displaystyle 2^{\omega }}$${\displaystyle [0,1]}$ ${\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 }}$

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

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

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

Реализация [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]