3
$\begingroup$

I ask this question because of some statements in the question "What is the 'continuity' as a term in computable analysis?" making me suspicious.

I'm engineer, not computer scientist, so I don't have the Turing machine but logic gates in mind when I'm thinking about algebraic operations performed with devices.

I read the answer to the question "Why are computable functions continuous?" and understood it the following way:

Because the device's input is of infinite length (a decimal number with an infinite number of digits after the decimal point), the device (e.g. Turing machine or computer) cannot read the entire number before writing the $n$-th digit of output.

Instead, the device can only have read $m(n)$ digits of the input when it writes the $n$-th digit of output.

If the first $n$ digits of the output of some function only depend on the first $m(n)$ digits of the input, the function is continuous.

However, if I understand this argumentation correctly, the word "continuous" in computation theory is not identical to the word "continuous" in mathematics:

Rounding towards zero would only require reading the input until the decimal point (so $m(n)=\text{const.}$); however, the mathematical function being calculated is not "continuous" according to the mathematical definition of that term.

We could also perform a digit-wise operation ($m(n)=n$) and exchange certain digits after the decimal point; for example replace all 4s by 9s and all 9s by 4s. As far as I understand, the function being calculated is not continuous on any interval of $\mathbb{R}$ (however, it would be right-continuous on $[0,\infty)$ and left-continuous on $(-\infty,0]$).

And if I didn't make a conceptual mistake and we use a balanced numeral system (like a Russian computer in the 1960s) instead of the decimal system, a similar algorithm (exchanging 0s and 1s instead of 4s and 9s) would even represent a mathematical function which is not even directional continuous on any interval of $\mathbb{R}$.

Questions:

Does the computability depend on the numeral system being used (as the example with the balanced numeral system suggests) or is the term "computable" even assuming a certain numeral system being used?

Is the observation correct that the term "continuous" does not have the same meaning in maths and CS?

$\endgroup$
6
  • $\begingroup$ I'm not sure if your title accurately captures what you are asking here. I think most people in CS (theoretical or not) would think about the mathematical/topological meaning of "continuity" when used in isolation. Thus, "continuity" means the same thing in the two fields in that sense. However, the type of "continuity" in the other question is different from the usual notion, as can be seen from the definition given in the currently accepted answer. So, your titular question is easily answered, but that doesn't seem to be what you're looking for. $\endgroup$ – Discrete lizard Aug 24 '20 at 8:38
  • $\begingroup$ @Discretelizard Not being a computer scientist, it is maybe hard to describe correctly what I want to know. However, my main problem is why it is said that some functions (like rounding towards zero) are said not to be computable on $\mathbb{R}$ although there is an algorithm that can perform the calculation. $\endgroup$ – Martin Rosenau Aug 24 '20 at 8:47
  • $\begingroup$ Well, maybe you should change your title into something like "why are some functions said to be not computable on the real numbers even though it seems there is an algorithm that can compute them?", then. $\endgroup$ – Discrete lizard Aug 24 '20 at 9:05
  • $\begingroup$ @Discretelizard I agree that if the definition I gave in the answer were not equivalent to the usual topological notion on the reals, I'd be hard pressed to argue that mine is "the CS notion". However, they are equivalent. $\endgroup$ – Arno Aug 24 '20 at 9:05
  • 1
    $\begingroup$ A title that would express the question more precisely would be "Does the term continuity for real functions have a different meaning in topology and computable analysis?". $\endgroup$ – Arno Aug 24 '20 at 9:09
4
$\begingroup$

If we were to use the decimal expansion to represent real numbers, your reasoning would work. But that gives us a very badly behaved notion of computability:

Proposition: Multiplication by 3 is not computable relative to the decimal representation.

Proof: Assume the input starts 0.3333333... At some point, our computation needs to start outputting something. The best choices are 0. and 1.. In the first case, we have screwed up if our input has a 4 as next digit we hadn't looked at; in the second case a 2 makes us wrong. Thus, we cannot output a guaranteed prefix of the solution.

Using a different base would yield a different notion of computability, but none of them are suitable. Some ways that all yield the same good notion of computability are:

  1. Code a real $x$ as a sequence of rationals $(q_n)_{n \in \mathbb{N}}$ such that $|x - q_n| < 2^{-n}$.
  2. Code a real via a signed digit representation, using $\{-1,0,1\}$.
  3. Code a real $x$ as a sequence of rational intervals $(I_n)_{n \in \mathbb{N}}$ with $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

When we speak about computability of a function on the reals without specifying what kind of representation we are using, we mean one of these (or another equivalent one). This is just like we don't always point out using the Euclidean topology on the reals if we do, that is just the standard case. We can now state:

Theorem: The functions on the reals which are computable (wrt the standard representation) relative to some oracle are exactly the continuous functions (wrt the Euclidean topology).

Coming back to rounding, this shows that perfectly exact rounding cannot work. However, we can circumvene this by not restricting ourselves to functions. For example, the following task is computable:

Given a real number $x \in [0,1]$, output either $0$ or $1$. If $x < 0.501$, then $0$ is an acceptable solution and if $x > 0.499$, then $1$ is an acceptable solution.

If the input to the task above is from $[0.499,0.501]$, then the answer we get does not only depend on the real we are looking at, but on the particular code for that real that our algorithm reads. That can make reasoning about algorithms slightly more cumbersome, but we really can't avoid that.

$\endgroup$
5
  • $\begingroup$ But the representation $\lbrace -1,0,1\rbrace$ would be the balanced ternary system. Right? In this case the "exchange all 0s and all 1s" algorithm would calculate a well-defined mathematical function which is not continuous... $\endgroup$ – Martin Rosenau Aug 24 '20 at 9:20
  • $\begingroup$ $[0.1(-1)1(-1)....] = [0.0101...]$, but $[1.0(-1)0(-1)...] \neq [1.1010...]$ (the number on the left is below $1$, the one on the right is greater than $1$). So your algorithm does not compute a function on the reals. $\endgroup$ – Arno Aug 24 '20 at 9:24
  • $\begingroup$ I see. I wanted to replace the digits after the decimal point only; however in this case $0.\overline{10}$ would not be equal to $0.\overline{0(-1)}$... So the function is indeed not well-defined. Thanks for your answer. $\endgroup$ – Martin Rosenau Aug 24 '20 at 9:41
  • $\begingroup$ Sidenote: I think it's a convention to write $-1$ as $\text{T}$ in a balanced ternary numeral...? $\endgroup$ – Dannyu NDos Aug 24 '20 at 11:36
  • $\begingroup$ I think that the sentence "Using a different base would yield a different notion of computability..." helped me with my problem in understanding: I have to decide if I want a numeral system allowing me to calculate non-continuous functions or one allowing me to calculate basic operations like the multiplications but I can't have both. However, with the "correct" numeral system I could calculate functions like sign()... $\endgroup$ – Martin Rosenau Aug 29 '20 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.