Вычислимый анализ - Computable analysis

В математика и Информатика, вычислимый анализ это изучение математический анализ с точки зрения теория вычислимости. Это касается частей реальный анализ и функциональный анализ что может быть выполнено в вычислимый манера. Поле тесно связано с конструктивный анализ и численный анализ.

Основные конструкции

Популярной моделью для выполнения вычислимого анализа являются: Машины Тьюринга. Конфигурация ленты и интерпретация математических структур описываются следующим образом.

Машины Тьюринга 2-го типа

Машина Тьюринга 2-го типа - это машина Тьюринга с тремя лентами: входная лента, доступная только для чтения; рабочая лента, на которую можно записывать и читать; и, в частности, выходная лента, предназначенная только для добавления.

Действительные числа

В этом контексте действительные числа представлены как произвольные бесконечные последовательности символов. Эти последовательности могут, например, представлять цифры действительного числа. Такие последовательности не обязательно должны быть вычислимы. С другой стороны, программы, которые действуют на эти последовательности делать должны быть вычислимыми в разумном смысле.

Вычислимые функции

Вычислимые функции представлены в виде программ на машине Тьюринга 2-го типа. Программа считается Всего (в смысле общие функции в отличие от частичные функции ), если требуется конечное время для записи любого количества символов на выходную ленту независимо от входа. Программы работают вечно, генерируя на выходе все больше цифр.

Имена

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

Обсуждение

Проблема вычислимости Типа 1 и Типа 2

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

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

Реализуемость

Если кто-то недоволен использованием машин Тьюринга (на том основании, что они низкоуровневые и несколько произвольные), есть возможность реализации называется топосом Клини-Весли, в котором вычислимый анализ к конструктивный анализ. Этот конструктивный анализ включает в себя все, что действует в школе Брауэра, а не только в школе епископа.

Основные результаты

Каждая вычислимая действительная функция есть непрерывный (Weihrauch 2000, стр. 6).

Арифметические операции над действительными числами вычислимы.

Существует подмножество реальных чисел, называемое вычислимые числа, что по приведенным выше результатам является настоящее закрытое поле.

В то время равенство отношения не разрешимый, предикат "больше" для неравных действительных чисел разрешим.

В единая норма оператор также вычислим. Отсюда следует вычислимость интегрирования Римана.

В Интеграл Римана является вычислимым оператором: другими словами, существует алгоритм, который численно вычисляет интеграл любого вычислимая функция.

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

Аналогия между общей топологией и теорией вычислимости

Один из основных результатов вычислимого анализа состоит в том, что каждый вычислимая функция от ${displaystyle mathbb {R} }$ к ${displaystyle mathbb {R} }$ является непрерывный (Weihrauch 2000, стр. 6). Если пойти дальше, это говорит о том, что существует аналогия между основными понятиями топологии и основными понятиями вычислимости:

• Вычислимые функции аналогичны непрерывным функциям.
• Полуразрешимый наборы аналогичны открытые наборы.
• Ко-полуопределимые множества аналогичны закрытые наборы.
• Существует вычислимый аналог топологической компактность. А именно подмножество ${displaystyle S}$ из ${displaystyle mathbb {R} }$ является вычислимо компактный если есть процедура полурешения "${displaystyle forall _{S}}$"что, учитывая полуразрешимый предикат ${displaystyle P}$ в качестве входных данных частично определяет, будет ли каждая точка в наборе ${displaystyle S}$ удовлетворяет предикату ${displaystyle P}$.
• Приведенное выше понятие вычислимой компактности удовлетворяет аналогу Теорема Гейне-Бореля. В частности, единичный интервал ${displaystyle [0,1]}$ вычислимо компактно.
• Дискретные множества в топологии аналогичны множествам в вычислимости, где равенство между элементами является полуразрешимым.
• Множества Хаусдорфа в топологии аналогичны множествам в вычислимости, где неравенство между элементами является полуразрешимым.

Аналогия предполагает, что общая топология и вычислимость почти зеркальные отражения друг друга. Аналогию можно объяснить тем, что теория вычислимости и общая топология могут быть выполнены с использованием конструктивной логики.

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

• Последовательность Спекера

использованная литература

• Оливер Аберт (1980), Вычислимый анализ, Макгроу-Хилл, ISBN  0-0700-0079-4.
• Мариан Пур-Эль и Ян Ричардс (1989), Вычислимость в анализе и физике, Springer-Verlag.
• Стивен Г. Симпсон (1999), Подсистемы арифметики второго порядка.
• Клаус Вейрах (2000), Вычислимый анализ, Спрингер, ISBN  3-540-66817-9.

внешние ссылки

• Вычислимость и сложность в аналитической сети