Is the function, calculating square root of natural number -- computable?

Question

My question is about domain of the term "computable".

Consider Turing machine, that calculates square roots of natural numbers.

If it gets

4

then it prints out

2 
.

and stops.

If it gets

9

then in prints out

3
.

ans stops.

And if it gets

2

then in prints

1
.
4
1

and never stops, continuing printing of decimal digits of $\sqrt{2}$.

Does this mean, that sqrt function is not computable, by definition of computable function?

UPDATE

Is nullary (of zero arity) function $f()=\sqrt{2}$ is classified as "not computable function"?

UPDATE 2

I need just a confirmation, that $f(x)=const=\sqrt{2}$ is named "not computable function" and simultaneously $\sqrt{2}=1.41...$ is named "computable number". I.e. term "computable" is inconsistent.

I deduce this from textbooks, but since I am not mathematician I can't believe myself. Need authoritative confirmation.

Answer 1

There are a few issues that I think you are getting confused about:

1. Computability theory is, fundamentally, about computable functions. The first step in understanding any new aspect of computability theory is to ask: what function or type of function is being considered?

2. Computability theory, more than most other areas of mathematics, is typed. In most areas of mathematics, the real number 2, the integer 2, and the natural number 2 can be treated as the same object. This is not the case in computability: each type of number or mathematical object is different, because they are represented ("coded") in different ways for the purposes of computability.

With that in mind, there are different notions of "computable function" depending on what type of objects make up the domain of the function and what type of objects make up the range of the function. The first definition that is usually encountered is the definition for partial functions from $\mathbb{N}$ to $\mathbb{N}$.

Definition 1. A partial function $f$ from $\mathbb{N}$ to $\mathbb{N}$ is computable if and only if there is a Turing machine that, when run with input $x$, will halt with output $f(x)$, whenever $f(x)$ is defined, or will not halt at all, if $f(x)$ is not defined.

There are many other characterizations of the partial computable functions from $\mathbb{N}$ to $\mathbb{N}$, of course.

Definition 1 says nothing about the computability of a function from $\mathbb{R}$ to $\mathbb{R}$. But there is a definition of that kind of computability - it's just that it is a different definition because it concerns objects of a different type. Because the input is now an infinite object (a representation of an element of $\mathbb{R}$) and the output is formally also an infinite object, the definition has to be different. One way to phrase it is in terms of oracle Turing machines.

The definition also uses what are called quickly converging Cauchy sequences. A sequence $(q_n)$ of rational numbers is called a quickly converging Cauchy sequence if, for all $n < m$, $|q_n - q_m| < 2^{-n}$. The key facts are that:

1. Every real number is the limit of at least one quickly converging Cauchy sequence of rational numbers.

2. Every quickly converging Cauchy sequence of rationals converges to some real number.

3. If $L$ is the limit of a quickly converging Cauchy sequence $(q_n)$, then for all $n$, $|L-q_n| \leq 2^{-n}$. So given any $K \in \mathbb{N}$ we can effectively find an $n$ with $|L-q_n| < 1/K$.

As an example: for any real number $r$, the sequence of partial decimal expansions of $r$ is a quickly converging Cauchy sequence, e.g. $$ 1, 1.4, 1.41, 1.414, 1.4142, \ldots $$ is a quickly converging Cauchy sequence for $\sqrt{2}$.

With this in mind, we can define computability for real functions. Informally, the idea is that when given a quickly converging Cauchy sequence for a real number $x$ as an oracle, the machine computes a quickly converging Cauchy sequence that converges to $F(x)$.

Definition 2. A function $F$ from $\mathbb{R}$ to $\mathbb{R}$ is computable if there is an oracle Turing machine which does the following: whenever the machine is run with the oracle tape containing an enumeration $E$ of a quickly converging Cauchy sequence, and a number $n$ on the input tape, the machine halts with an output $q_n^E$ which is a code for a rational number. Moreover, as long as $E$ is a quickly converging Cauchy sequence, the sequence $(q_n^E)$ is a quickly converging Cauchy sequence, and if $x = \lim E$ then $F(x) = \lim q_n^E$.

Definition 2 can be generalized to allow for many other types of input objects, in what is called "type 2 computability". The book Computable Analysis by Klaus Weihrauch has more information about that. It also has a nice survey of definitions of real-number computation in Chapter 9.

There is also a definition of a computable real number:

Definition 3. A real number $r$ is computable if there is a Turing machine that computes a quickly converging Cauchy sequence that converges to $r$. In other words, the machine computes a total function $f\colon \mathbb{N} \to \mathbb{N}$ such that, if we view each $f(n)$ as a code for a rational number $q_n$, then $(q_n)$ is a quickly converging Cauchy sequence and $r = \lim q_n$.

There is no contradiction between Definitions 1, 2, and 3: they all define certain kinds of computability.

• The natural-number square root function from $\mathbb{N}$ to $\mathbb{N}$ is a partial function and it is computable in the sense of Definition 1.

• The real-number square root function from $[0,\infty)$ to $[0,\infty)$ is computable in the sense of Definition 2. Here we add the assumption that the limit of the input Cauchy sequence is nonnegative.

• The real number $\sqrt{2}$ is computable in the sense of Definition 3.

Finally, the strange definition that is on this version of the Wikipedia article "computable real function" is flawed. To be fair to Wikipedia, it seems to be copied from the PlanetMath article "computable real function". That definition was probably obtained by taking a reasonable definition for a computable function on a closed, bounded interval $[a,b]$, and then replacing the interval with $\mathbb{R}$. But, according to that definition, not even the multiplication function on real numbers is computable, because it is not uniformly continuous. The multiplication function on real numbers is computable in the sense of Definition 2 (where now there are two oracle tapes for the two input numbers) and multiplication of real numbers is computable in any reasonable definition of computable real functions.

Answer 2

No, the set of functions is greater than the set of numbers. Part of this is due to the massive number of ways to compute numbers as if you consider how to compute a value like 4 there are more than a few ways to do it: 1+1+1+1, 2+2, 2*2, etc.

Computable function notes:

The set of finitary functions on the natural numbers is uncountable so most are not computable. Concrete examples of such functions are Busy beaver, Kolmogorov complexity, or any function that outputs the digits of a noncomputable number, such as Chaitin's constant.

Whereas, Computable number notes:

While the set of real numbers is uncountable, the set of computable numbers is only countable and thus almost all real numbers are not computable.

Yes, $\sqrt2$ is computable as a number but not as a function as one can get arbitrary precision from various algorithms. If you aren't familiar with it, I'd highly suggest studying the Halting problem as something that is useful here in considering whether or not some algorithm is finite and will terminate.

---

The example of a "non-computable number" is used because of what can be done to demonstrate that infinite precision can't be done in finite steps. That for any given maximum number of steps that is an element of $\mathbb{N}$, there will exist this number plus one that is also in $\mathbb{N}$ which violates the ability to compute it with more precision. As an alternative consider what is the biggest number you could write out and consider that there may well be a bigger number that could be written had you lived a bit longer.

The complex examples are likely due to wanting something that is non-trivial to initially approximate. While $\sqrt2$ could be used, there are likely more than a few people that would misinterpret this result and want to go, "Well, if I can't get infinite precision, I'm not doing this!" which wouldn't be good for Math teachers trying to teach this material to students.