computable sequence

A sequence ${\{r_i\}}_{i=0}^{\mathrm{\infty }}$ of rational numbers is called computable if there exist recursive functions $F:\mathbb{N}\to \mathbb{Z}$ and $G:\mathbb{N}\to \mathbb{N}\setminus \{0\}$ such that

$$r_i=\frac{F(i)}{G(i)}.$$

A sequence ${\{r_i\}}_{i=0}^{\mathrm{\infty }}$ of real numbers is called computable if there exists a recursive functions $F:{\mathbb{N}}^2\to \mathbb{Z}$ such that

Note that, although every computable sequence of real numbers is a sequence of computable real numbers, not every sequence of computable real numbers is a computable sequence of real numbers. Formally, this is the case because the set of computable sequences of real numbers is countable (its cardinality cannot be greater than that of the set of recursive functions) whilst the set of sequences of computable real numbers is uncountable (by Cantor’s diagonal argument).

An explanation of this fact which, if somewhat less rigorous, is more satisfying to the intuition is the following: Imagine a sequence of computable real numbers such that the shortest FORTRAN program which could calculate the first number to arbitrarily specified precision is at least 1 kilobyte long, the shortest FORTRAN program which which could calculate the second number to arbitrarily specified precision is at least 2 kilobytes long, the shortest FORTRAN program which could calculate the third number to arbitrarily specified precision is at least 3 kilobytes long, and so on. If this sequence were computable, there would exist a finite FORTRAN program that would compute the recursive function $F$ that appears in the definition of computable sequence. By adding a few more lines of to such a program, one would have a program that could compute any element of the sequence to arbitrary precision. However, no such program could possibly exist because of the way that the sequence was defined, and hence this sequence is not a computable sequence even though each of its elements is a computable real number.