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

Question

Я задаю этот вопрос из-за некоторых утверждений в вопросе «Что такое «непрерывность» как термин в вычислимом анализе?» вызывая у меня подозрения.

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

Я прочитал ответ на вопрос «Почему вычислимые функции непрерывны?» и понял это так:

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

Вместо этого устройство может только читать $м(п)$ цифры ввода, когда он записывает $n$-я цифра вывода.

Если первый $n$ цифры вывода некоторой функции зависят только от первой $м(п)$ цифр входа, функция непрерывна.

Однако, если я правильно понимаю эту аргументацию, слово «непрерывный» в теории вычислений не идентично слову «непрерывный» в математике:

Округление в сторону нуля потребует чтения входных данных только до десятичной точки (поэтому $m(n)= ext{const.}$);однако вычисляемая математическая функция не является «непрерывной» согласно математическому определению этого термина.

Мы также могли бы выполнить цифровую операцию ($m(n)=n$) и поменять местами определенные цифры после запятой;например заменить все 4s by 9и все 9s by 4с.Насколько я понимаю, вычисляемая функция не является непрерывной ни на каком интервале $\mathbb{R}$ (однако оно было бы непрерывно справа на $[0,\infty)$ и непрерывный влево $(-\infty,0]$).

И если бы я не допустил концептуальную ошибку и мы воспользуемся сбалансированная система счисления (как Русский компьютер 1960-х годов.) вместо десятичной системы аналогичный алгоритм (замена 0песок 1s вместо 4песок 9s) даже представляло бы математическую функцию, которая даже не направленный непрерывный на любом интервале $\mathbb{R}$.

Вопросы:

Зависит ли вычислимость от используемой системы счисления (как предполагает пример со сбалансированной системой счисления) или термин «вычислимый» даже предполагает использование определенной системы счисления?

Верно ли наблюдение, что термин «непрерывный» не имеет одинакового значения в математике и информатике?

Answer 1

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

Предложение:Умножение на 3 не вычислимо относительно десятичного представления.

Доказательство:Предположим, что ввод начинается с 0,3333333...В какой-то момент наши вычисления должны начать что-то выводить.Лучший вариант — 0.и 1..В первом случае мы облажались, если в качестве следующей цифры в нашем вводе указана цифра 4, которую мы не учли;во втором случае 2 делает нас неправыми.Таким образом, мы не можем вывести гарантированный префикс решения.

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

1. Код настоящий $х$ как последовательность рациональных чисел $(q_n)_{n \in \mathbb{N}}$ такой, что $ | X - Q_N | <2^{-n} $.
2. Закодируйте вещественное число через представление цифр со знаком, используя $\{-1,0,1\}$.
3. Код настоящий $х$ как последовательность рациональных интервалов $(I_n)_{n \in \mathbb{N}}$ с $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

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

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

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

Учитывая действительное число $x \in [0,1]$, выведите либо $0$ или $1$.Если $х <0,501$, затем $0$ является приемлемым решением, и если $х > 0,499$, затем $1$ является приемлемым решением.

Если входные данные для задачи выше взяты из $[0.499,0.501]$, то ответ, который мы получим, зависит не только от реального, на которое мы смотрим, но и от конкретного кода для этого реального, который считывает наш алгоритм.Это может сделать рассуждения об алгоритмах немного более громоздкими, но мы действительно не можем этого избежать.