“连续性”一词在数学和计算机科学中具有不同的含义吗？

Question

我问这个问题是因为问题中的一些陈述 “可计算分析中的‘连续性’是什么？” 让我怀疑。

我是工程师，而不是计算机科学家，所以当我考虑使用设备执行代数运算时，我想到的不是图灵机，而是逻辑门。

我读了问题的答案 “为什么可计算函数是连续的？” 并通过以下方式理解它：

因为设备的输入是无限长度的（小数点后有无限位数的十进制数），所以设备（例如图灵机或计算机）在写入之前无法读取整个数字 $n$输出的第 - 位数字。

相反，设备只能读取 $m(n)$ 写入时输入的数字 $n$输出的第 - 位数字。

如果第一个 $n$ 某些函数输出的数字仅取决于第一个 $m(n)$ 输入的数字，函数是连续的。

然而，如果我正确理解这个论证，计算理论中的“连续”一词与数学中的“连续”一词并不相同：

四舍五入到零只需要读取输入直到小数点（所以 $m(n)= ext{常量}$）；然而，根据该术语的数学定义，正在计算的数学函数不是“连续的”。

我们还可以执行数字运算（$m(n)=n$) 并交换小数点后的某些数字；例如替换所有 4是由 9和所有 9是由 4s。据我了解，正在计算的函数在任何间隔上都不连续 $\mathbb{R}$ （但是，这将是右连续的 $[0,\infty)$ 和左连续 $(-\infty,0]$).

如果我没有犯概念错误并且我们使用 平衡数制 （像一个 20 世纪 60 年代的俄罗斯计算机）代替十进制，类似的算法（交换 0沙 1s 而不是 4沙 9s) 甚至可以表示一个数学函数 甚至不是定向连续的 在任意区间 $\mathbb{R}$.

问题：

可计算性是否取决于所使用的数字系统（如平衡数字系统的示例所示），或者术语“可计算”甚至假设使用某种数字系统？

“连续”一词在数学和计算机科学中的含义不同，这一观察是否正确？

Answer 1

如果我们使用十进制展开来表示实数，你的推理就会成立。但这给了我们一个非常糟糕的可计算性概念：

主张: ：相对于十进制表示法，乘以 3 是不可计算的。

证明: ：假设输入从 0.3333333 开始...在某些时候，我们的计算需要开始输出一些东西。最好的选择是 0。和 1..在第一种情况下，如果我们的输入有一个 4 作为我们没有看过的下一个数字，我们就搞砸了；在第二种情况下，a 2 让我们错了。因此，我们无法输出有保证的解的前缀。

使用不同的基数会产生不同的可计算性概念，但它们都不合适。所有产生相同的可计算性概念的一些方法是：

1. 编码一个真实的 $x$ 作为有理数序列 $(q_n)_{n \in \mathbb{N}}$ 这样 $ | x -q_n | <2^{ - n} $.
2. 通过带符号的数字表示形式编码实数，使用 $\{-1,0,1\}$.
3. 编码一个真实的 $x$ 作为有理区间的序列 $(I_n)_{n \in \mathbb{N}}$ 和 $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

当我们谈论实数函数的可计算性而不指定我们使用哪种表示形式时，我们指的是其中之一（或另一个等效的表示形式）。这就像我们并不总是指出在实数上使用欧几里得拓扑（如果我们这样做的话），这只是标准情况。我们现在可以声明：

定理: ：相对于某些预言的可计算的实数函数（相对于标准表示）正是连续函数（相对于欧几里得拓扑）。

回到舍入，这表明完全精确的舍入是行不通的。然而，我们可以通过不将自己限制在函数上来规避这个问题。例如，以下任务是可计算的：

给定一个实数 $x \in [0,1]$, ，输出任一 $0$ 或者 $1$. 。如果 $x < 0.501$, ， 然后 $0$ 是一个可接受的解决方案，如果 $x > 0.499$, ， 然后 $1$ 是一个可以接受的解决方案。

如果上述任务的输入来自 $[0.499,0.501]$, ，那么我们得到的答案不仅取决于我们正在查看的实数，还取决于我们的算法读取的实数的特定代码。这可能会使算法的推理变得稍微麻烦一些，但我们确实无法避免这一点。