Вычислимый анализ

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

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

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

Основные конструкции [ править ]

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

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

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

Действительные числа [ править ]

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

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

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

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

Вычислимые функции [ править ]

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

Имена [ править ]

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

Обсуждение [ править ]

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

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

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

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

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

Основные результаты [ править ]

Любая вычислимая действительная функция непрерывна . ^[7]

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

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

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

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

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

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

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

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

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

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

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

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

Примечания [ править ]

^ См. Симпсон, Алекс К. (1998), Брим, Любош; Грушка, Йозеф; Златушка, Иржи (ред.), «Ленивые функциональные алгоритмы для точных вещественных функционалов» , Математические основы информатики, 1998 г. , Конспекты лекций по информатике, том. 1450, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 456–464, doi : 10.1007/bfb0055795 , ISBN 978-3-540-64827-7
^ по интегральной формуле Коши.
^ потому что разрывные операторы автоматически невычислимы.
^ Невычислимое действительное число может быть сгенерировано с почти наверняка путем случайной выборки каждой цифры в бесконечном бесконечном процессе.
^ Бауэр, Андрей. «Лемма Кенига и дерево Клини» (PDF) .
^ Юмпу.com. «Реализуемый подход к вычислительному анализу… — Андрей Бауэр» . yumpu.com . Проверено 18 августа 2023 г.
^ Перейти обратно: ^а ^б Вайраух 2000, с. 6.
^ Майхилл, Дж. (1971). «Рекурсивная функция, определенная на компактном интервале и имеющая непрерывную производную, которая не является рекурсивной» . Мичиганский математический журнал . 18 (2). дои : 10.1307/mmj/1029000631 . ISSN 0026-2285 .
^ «абстрактная двойственность Стоуна в nLab» . ncatlab.org . Проверено 29 июля 2023 г.

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

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

Внешние ссылки [ править ]

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

[1] См. Симпсон, Алекс К. (1998), Брим, Любош; Грушка, Йозеф; Златушка, Иржи (ред.), «Ленивые функциональные алгоритмы для точных вещественных функционалов» , Математические основы информатики, 1998 г. , Конспекты лекций по информатике, том. 1450, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 456–464, doi : 10.1007/bfb0055795 , ISBN 978-3-540-64827-7

[2] по интегральной формуле Коши.

[3] потому что разрывные операторы автоматически невычислимы.

[4] Невычислимое действительное число может быть сгенерировано с почти наверняка путем случайной выборки каждой цифры в бесконечном бесконечном процессе.

[5] Бауэр, Андрей. «Лемма Кенига и дерево Клини» (PDF) .

[6] Юмпу.com. «Реализуемый подход к вычислительному анализу… — Андрей Бауэр» . yumpu.com . Проверено 18 августа 2023 г.

[:0-7] Перейти обратно: ^а ^б Вайраух 2000, с. 6.

[8] Майхилл, Дж. (1971). «Рекурсивная функция, определенная на компактном интервале и имеющая непрерывную производную, которая не является рекурсивной» . Мичиганский математический журнал . 18 (2). дои : 10.1307/mmj/1029000631 . ISSN 0026-2285 .

[9] «абстрактная двойственность Стоуна в nLab» . ncatlab.org . Проверено 29 июля 2023 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]