Вычислимая аналитика

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

Примечательным результатом является то, что интегрирование (в смысле интеграла Римана ) вычислимо. ^[1] Это можно было бы счесть удивительным, поскольку интеграл (грубо говоря) является бесконечной суммой. Хотя этот результат можно было бы объяснить тем фактом, что каждая вычислимая функция из в равномерно непрерывна , примечательным является то, что модуль непрерывности всегда можно вычислить, не будучи явно заданным. Аналогичным удивительным фактом является то, что дифференцирование комплексных функций также вычислимо, в то время как тот же результат ложен для действительных функций ; см. § Основные результаты. ${\displaystyle \mathbb {[} 0,1]}$ ${\displaystyle \mathbb {R} }$

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

Базовые конструкции

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

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

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

Реальные цифры

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

В случае действительных чисел обычные десятичные или двоичные представления не подходят. Вместо этого часто используется знаковое цифровое представление, впервые предложенное Брауэром: Система счисления имеет основание 2, но цифры (представляющие ), 0 и 1. В частности, это означает, что их можно представить как и . ${\displaystyle {\overline {1}}}$ ${\displaystyle -1}$ ${\displaystyle 1/2}$ ${\displaystyle 0.1}$ ${\displaystyle 1.{\overline {1}}}$

Чтобы понять, почему десятичная запись неуместна, рассмотрим задачу вычисления , где и , и предоставления результата в десятичной записи. Значение равно или . Если бы был дан последний результат, например, то конечное число цифр из было бы прочитано до выбора цифры перед десятичной точкой в ​​— но затем, если бы th цифра из была уменьшена до 2, то результат для был бы неверным. Аналогично, предыдущий выбор для иногда был бы неверным. Это, по сути, дилемма изготовителя таблиц . ${\displaystyle z=x+y}$ ${\displaystyle x=0.(3)}$ ${\displaystyle y=0.(6)}$ ${\displaystyle z}$ ${\displaystyle z}$ ${\displaystyle 0.(9)}$ ${\displaystyle 1.(0)}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle 1}$ ${\displaystyle z}$ ${\displaystyle n+1}$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle 0.(9)}$ ${\displaystyle z}$

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

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

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

Имена

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

Обсуждение

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

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

Разница между двумя моделями заключается в том, что программа, которая хорошо себя ведет над вычислимыми числами (в смысле тотальности), не обязательно хорошо себя ведет над произвольными действительными числами. Например, существуют вычислимые функции над вычислимыми действительными числами, которые отображают некоторые ограниченные замкнутые интервалы в неограниченные открытые интервалы. ^[3] Эти функции не могут быть расширены до произвольных действительных чисел (не делая их частичными), поскольку все вычислимые функции непрерывны, и это тогда нарушило бы теорему об экстремальном значении . Поскольку такое поведение можно считать патологическим, естественно настаивать на том, что функция должна считаться тотальной, только если она тотальна над всеми действительными числами, а не только над вычислимыми. ${\displaystyle \mathbb {R} \to \mathbb {R} }$

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

В случае, если кто-то недоволен использованием машин Тьюринга (на том основании, что они являются низкоуровневыми и несколько произвольными), существует топос реализуемости, называемый топосом Клини -Весли, в котором можно свести вычислимый анализ к конструктивному анализу . Этот конструктивный анализ включает в себя все, что справедливо в школе Брауэра, а не только в школе Бишопа. ^[4] Кроме того, теорема в этой школе конструктивного анализа заключается в том, что не все действительные числа вычислимы , что конструктивно не эквивалентно тому, что существуют невычислимые числа . Таким образом, эта школа конструктивного анализа находится в прямом противоречии со школами конструктивного анализа — такими как Марковская, — которые утверждают, что все функции вычислимы. В конечном итоге это показывает, что, хотя конструктивное существование подразумевает вычислимость, на самом деле непроблематично — даже полезно — утверждать, что не каждая функция вычислима.

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

• Каждая вычислимая действительная функция непрерывна . ^[5]
• Арифметические операции над действительными числами вычислимы.
• В то время как отношение равенства неразрешимо , предикат « больше, чем» для неравных действительных чисел разрешим.
• Оператор равномерной нормы также вычислим. Это подразумевает вычислимость интегрирования Римана.
• Интеграл Римана — вычислимый оператор: Другими словами, существует алгоритм, который численно вычислит интеграл любой вычислимой функции .
• Оператор дифференциации над действительными функциями невычислим , но над комплексными функциями вычислим . Последний результат следует из интегральной формулы Коши и вычислимости интегрирования. Первый отрицательный результат следует из того факта, что дифференциация (над действительными функциями) разрывна . [ ^6] Это иллюстрирует пропасть между действительным анализом и комплексным анализом , а также сложность численного дифференцирования над действительными числами, которую часто обходят, расширяя функцию до комплексных чисел или используя символические методы.
• Существует подмножество действительных чисел, называемое вычислимыми числами , которое согласно приведенным выше результатам является действительным замкнутым полем .

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

Одним из основных результатов вычислимого анализа является то, что каждая вычислимая функция из в является непрерывной . ^[5] Развивая это дальше, можно предположить, что существует аналогия между основными понятиями топологии и основными понятиями вычислимости: ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$

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

Аналогия предполагает, что общая топология и вычислимость являются почти зеркальными отражениями друг друга. Аналогия была сделана строгой в случае локально компактных пространств . ^[7] Это привело к созданию подобластей общей топологии, таких как теория доменов , которые изучают топологические пространства, очень непохожие на пространства Хаусдорфа, изучаемые большинством людей в математическом анализе — эти пространства становятся естественными в рамках аналогии.

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

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

Примечания

1. См. Симпсон, Алекс К. (1998), Брим, Любош; Грушка, Йозеф; Златушка, Йиржи (ред.), «Ленивые функциональные алгоритмы для точных вещественных функционалов», Математические основы компьютерной науки 1998 , Lecture Notes in Computer Science, т. 1450, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 456–464, doi :10.1007/bfb0055795, ISBN 978-3-540-64827-7
2. Невычислимое действительное число можно сгенерировать почти наверняка, выбирая каждую цифру случайным образом в бесконечном, непрекращающемся процессе.
3. Бауэр, Андрей. «Лемма Кёнига и дерево Клини» (PDF) .
4. Yumpu.com. "Подход к вычислимому анализу с точки зрения реализуемости... - Андрей Бауэр". yumpu.com . Получено 18.08.2023 .
5. Weihrauch 2000, стр. 6.
6. Myhill, J. (1971). «Рекурсивная функция, определенная на компактном интервале и имеющая непрерывную производную, которая не является рекурсивной». Michigan Mathematical Journal . 18 (2). doi : 10.1307/mmj/1029000631 . ISSN  0026-2285.
7. "abstract Stone duality in nLab". ncatlab.org . Получено 29.07.2023 .

Ссылки

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

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

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