3

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.

Carl Mummert
  • 81,604
Dims
  • 1,149
  • 2
    A number $x$ is computable if there is an algorithm which, given $n$, calculates the first $n$ digits of $x$ and halts. $\pi$ is computable in this sense. I think that rather than trying to learn these concepts a piece at a time by asking questions here, you would do better to read a book, or perhaps just the Wikipedia articles, and then come back and ask about the parts you didn't understand. – MJD Aug 08 '13 at 14:56
  • I understand the definitions, but can't believe they are not consistent. More reading won't help. Please confirm that definitions are inconsistent. Or fix me if they does not. – Dims Aug 08 '13 at 14:57
  • 2
    I don't think you do understand them, and my previous comment tried to fix you about the definition of "computable number". – MJD Aug 08 '13 at 15:00
  • I guess my definiton was equivalent to yours. I said "to any given precision" and you said "to any given $n$ where $n$ is a number of first digits". If this is different then pls explain. – Dims Aug 08 '13 at 15:08
  • @Dims What precisely do you mean by "can be calculated"? – Andrés E. Caicedo Aug 08 '13 at 16:05
  • 2
    You are mixing things up. In particular, the confusion seems to come from not distinguishing between computable in the sense of Turing machines, and computable for real functions, as in this Wikipedia entry. – Andrés E. Caicedo Aug 08 '13 at 16:46
  • @AndresCaicedo so is there a concept of "computable real functions" which is consistent with concept of "computable (real) numbers"? – Dims Aug 08 '13 at 16:48
  • $\sqrt{2}<2$, so not sure why you are writing $\sqrt{2}=2.41\dots$. – Thomas Andrews Aug 08 '13 at 16:59
  • 2
    The basic notion of computability (in this context) is that of functions from $\mathbb N$ to $\mathbb N$. You can speak of other things being computable only after you encode them in this form. It doesn't make sense to ask a Turing machine to print all the digits of $\sqrt2$, any more than it makes sense to ask it to print all of the even numbers in $\mathbb N$. Instead, we call $\sqrt2$ a computable number because you can build a Turing machine which, given a natural number $n$, yields the $n$th digit of $\sqrt2$ in finite time; the $n$th digit of $\sqrt2$ is a computable function. –  Aug 08 '13 at 18:00
  • @RahulNarain my question is about terms; If I have real function and CAN NOT (in principle) find representation in $\mathbb{N}\rightarrow\mathbb{N}$ form, then what does it means? That function is "not computable"? Or term "computable" is not applicable for real functions at all? If not, then is there any equivalent concept for real functions? – Dims Aug 08 '13 at 19:05

2 Answers2

8

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.

Carl Mummert
  • 81,604
0

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.

JB King
  • 3,644
  • If so, then why it is said in your citation, that not computable functions examples are "any function that outputs the digits of a noncomputable number, such as Chaitin's constant"? Why such complex examples if such simple function, as the one computing digits of $\sqrt{2}$ is also not computable? – Dims Aug 08 '13 at 15:46