Какова «непрерывность» как термин в вычислимом анализе?

Question

фон

Я когда-то реализовал тип данных, представляющий произвольные реальные числа в Haskell. Это этикетки каждые реальные числа, имея последовательность Коши, сходящейся к ней. Это позволит $ \ mathbb {r} $ быть в обычной топологии. Я также реализовал дополнение, вычитание, умножение и разделение.

Но мой учитель сказал: «Это, похоже, не является хорошей идеей. Поскольку сравнение здесь неразрешимо, это не выглядит очень практично. В частности, позволяя делить на 0, чтобы упасть в бесконечную петлю не хорошо выглядеть. "

Так что я хотел, чтобы мой тип данных продлить $ \ mathbb {Q} $ . С момента сравнения равенства $ \ mathbb {q} $ - это решительно, $ \ mathbb {q} $ В дискретной топологии. Это означает, что топология на $ \ mathbb {r} $ должно быть более тонким, чем дискретная топология на $ \ mathbb {q} $ .

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

Доказательство, шаг 1

Пусть $ \ mathbb {r} $ Быть более чем $ \ mathbb {Q} $ в Дискретная топология. Тогда $ \ {0 \} $ открыт в $ \ mathbb {r} $ . Предположим, $ +: \ mathbb {r} ^ 2 → \ mathbb {r} $ непрерывно. Тогда $ \ {(x, -x): x \ in \ mathbb {r} \} $ открыт в $ \ mathbb {r} ^ 2 $ . Поскольку $ \ mathbb {r} ^ 2 $ находится в топологии продукта, $ \ {(x, -x) \} $ - это оснований элемент $ \ mathbb {r} ^ 2 $ для каждого $ x \ in \ mathbb {r} $ . Отсюда следует, что $ \ {x \} $ представляет собой основой элемент $ \ mathbb {r} $ Для каждого $ x \ in \ mathbb {r} $ . То есть $ \ mathbb {r} $ находится в дискретной топологии.

Доказательство, шаг 2

С момента $ \ mathbb {r} $ находится в дискретной топологии, $ \ mathbb {r} $ Вычислительно равенство сопоставимы. Это противоречие, так что $ + $ не является непрерывным, и, таким образом, не вычисляемым .

Вопрос

Что меня задумывает, это смелый текст. Хорошо известно, что каждая вычислимая функция непрерывна (Weihrauch 2000, стр. 6). Хотя аналитическое определение и топологическое определение непрерывности совпадают в функциях от и до евклидовых пространств, $ \ mathbb {R} $ выше не является евклидовым пространством. Так что я не уверен, правильно ли мое доказательство. Какое определение «непрерывность» в вычислимом анализе?

Answer 1

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

Определение : функция $ f: \ mathbf {x} \ to \ mathbf {y} $ непрерывно, если есть Вычислимая частичная функция $ f: \ subsEtq \ mathbf {x} \ times \ mathbb {n} ^ \ mathbb {n} \ to \ mathbf {y} $ и Некоторые $ p \ in \ mathbb {n} ^ \ mathbb {n} $ такой, что $ f (x)= f (x, p) $ .

Таким образом, самая примитивная концепция в обращении с пространством - это то, что мы используем для него, что затем дает понятие вычислимости, и от этого мы получаем понятие непрерывности.

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

Если у нас есть допустимое представление $ \ delta: \ subsEtq \ sigma ^ \ mathbb {n} \ to \ mathbf {x} $ , мы получаем топологию На $ \ mathbf {x} $ в качестве окончательной топологии вдоль $ \ Delta $ , то есть набор SPAN CLASS="MATH-CONSTERAR"> $ u \ subsretq \ mathbf {x} $ Открыто iff Есть установленный $ W $ конечных слов Такое, что $ \ delta ^ {- 1} (u)=\ {- 1} (u)=quellowname {dom} (\ delta) \ cap \ bigcup_ {w \ in w} w \ sigma ^ \ mathbb { N} $ . Матиас Шредер показал, что топологические пробелы, которые имеют допустимые представления, являются именно $ T_0 $ Cquenticle of ожирено на основе пробелов.

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

Есть способ получить допустимое представление $ \ mathbb {r} $ , который делает $ \ mathbb { Q} $ дискретное подпространство (по существу, лечить $ \ mathbb {r} $ как $ \ mathbb { N} ^ {*} \ cub \ mathbb {n} ^ \ mathbb {n} $ ), но, как вы утверждали в этом вопросе, что делает дополнение неискренне (и в целом, имеет очень мало сходства с реаламидами Как мы хотели бы их).

Набом Примечание, что мы не можем избежать застревания, даже не распознавая его, когда случайно пытается разделить на $ 0 $ - значительное препятствие, если мы пытаемся сделать Линейная алгебра с реальными числами.

<Сильные> Ссылки :

Питер Коллинз: Вычислимый анализ с приложениями к динамическим системам . Математика Распределять Высказываться Рассуждать 30 (2): 173-233 (2020)

Martín Hötzel Escardó: Синтетическая топология: типов данных и классических пространств . Электрон. Примечания Теору. Высказываться Рассуждать 87: 21-156 (2004)

Такаюки Кихара, Арно Поли: Разделение на ноль - как это плохо, действительно? MFCS 2016: 58: 1-58: 14

Арно Поли: Отопологические аспекты теории представленных пробелов . Вычислимость 5 (2): 159-180 (2016) arxiv

Matthias Schröder: Расширенная приемлемость . Theor. Высказываться Рассуждать 284 (2): 519-538 (2002)

Answer 2

Ответ Arno предоставляет некоторые очень полезные фоновые материалы для чтения, я просто хотел бы решить ваш конкретный вопрос о $ \ mathbb {r} $ .

Давайте сначала вспомним результат Питера Герти, см. Теорему 4.1 в Настоящая структура номера, которая эффективно категорическая ( PDF здесь), о вычислительной структуре вещественные числа. Предположим, у нас есть представление $ \ mathbb {r} $ , то есть структура данных, представляющая собой реальные, такие, что:

.
• $ 0 $ и 1 $ $ - вычислимые элементы $ \ mathbb {r} $ ,
• Полевые операции $ + $ , $ - $ , $ / $ вычислимы (где разделение на нуле, конечно, undefined)
• Оператор пределы, принимая быструю последовательность Cauchy к его пределу, является вычислимой (последовательность $ (x_n) _n $ быстро, когда $ | x_n - x_m | \ leq 2 ^ {- \ min (m, n)} $ ).
• строгий порядок $ < $ полувидный

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

Тогда следует, что:

1. Топология $ \ mathbb {r} $ - это стандартная евклидовая топология
2. равенство неразрешемо или эквивалентно, testng для нуля неразрешимо.
3. Любые две такие структуры вычислительно изоморфны.

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

Что касается вашей реализации: жизненно важно, чтобы вы представляете реальную последовательность Cauchy вместе с информацией , насколько быстро она сходится. Я надеюсь, что вы это сделали.