Example of a number that is not the limit of a computable sequence

Question

Let's define a real number as computable iff there's an algorithm that can generate a sequence with the number as its limit (turing machine or any of the equivalent programming models).

Not all real numbers fall into this category. In particular, the number of algorithms is countable.

My first question is how that concept is called in the research that probably exists on it.

The second question would be regarding the remaining real numbers. Is there an example for any such incomputable number that is well-defined?

So what I'm interested in is not a proof for existence - that one is trivial. I'm asking for a concrete example: To pick one of those numbers by defining it.

My feeling is that this is possible.

Answer 1

There seems to be a lot of confusion in the other answers and comments thereto. I'll try to make things more clear. (In particular, @Holowitz's and @Nico's answers are incorrect, as I showed in the comments below @Nico's answer.)

First note that a real number can be identified with a set of natural numbers by declaring that the binary expansion of the real corresponds to the characteristic sequence set of natural numbers. (Of course, some reals have non-unique binary expansion, so this identification doesn't always make sense, but any such real gives rise to a computable set no matter which binary expansion is taken, so insofar as we're concerned, this is irrelevant.)

Now, the definition of computable you gave is what's known as limit computable or $\Delta_{2}^{0}$, though since the notation $\Delta_{2}^{0}$ is a priori reserved for sets defined by formulas that are both $\Sigma_{2}^{0}$ and $\Pi^{0}_{2}$ in the arithmetical hierarchy, it must be proven that the two notions coincide. This is exactly Schoenfield's limit lemma together with Post's theorem.

Regarding your request for a "concrete" example of a real that is not $\Delta^{0}_{2}$ (i.e. one that can be "picked by defining it"), the number--let's call it $\alpha$--given in the paper cited in the answer you accepted is defined only relative to some fixed (incomputable!) enumeration of all $\Delta^{0}_{2}$ reals; different enumerations give rise to different $\alpha$'s. However, such an enumeration is inherently not $\Delta^{0}_{2}$ (it can be $\Delta^{0}_{3}$ as @Carl points out in the comments to @Mahmud's answer) in the arithmetical hierarchy, so I do think that it is an acceptable example (contrary to my comments) . Given that, though, it's evident that a much better (i.e. less complex) real can be given: take any strictly $\Sigma^{0}_{2}$ or $\Pi^{0}_{2}$ real. For example, the set of indices of total computable functions $\mathrm{Tot}:=\{e:\forall n \exists s \, [\varphi_{e,s}(n)\downarrow] \}$ is a well-known $\Pi^{0}_{2}$-complete real.

The moral of the story is that there are many arithmetically definable reals that are not "computable" in the sense you defined; just take any arithmetical real that is not $\Delta^{0}_{2}$.

Answer 2

Note: As Carl Mummert pointed out in the comments this answers the definition of a computable real number but NOT the one in question.

2.3. An example of non-computable real number

Let $C_b$ be the set of TMs computing real numbers belonging to [0, 1] and printing their digits in base $b$, let $k$ be the real number computed by the $k$-th machine of $C_b$ and $k(n)$ be the $n$-th digit of the number $k$. Consider the real number such that its $n$-th digit equals $n(n) + 1$ modulo $b$. For any $n$, differs from $n$ by its $n$-th digit. Thus does not belongs to $C_b$ and therefore is computable by no TM. Other examples of non-computable numbers are known: the Chaitin’s constant $Ω$ [2]; the real number such that its $n$-th digits equals 1 if a given universal TM halts for input $n$, and 0 otherwise (see[3]); the real number whose digits express the solutions of the busy beaver problem.

Reference:

Nicolas Brener. A definable number which cannot be approximated algorithmically. 2010

Answer 3

This answer is a response by to the answer by Mahmud. I want to show that the construction quoted there is underspecified, and that in at least one complete specification of it the answer is not correct for the general definition of computable numbers from the question. The answer is correct for the usual definition of computable real numbers.

Let $C$ be the set of all Turing machines that are total: for every $T \in C$ and every $n$, $T$ halts on input $n$. It is a standard fact that $C$ is $\Pi^0_2$ complete, so there is no computable enumeration of $C$. Hence the construction in the other answer must choose some noncomputable enumeration of $C$. We construct an enumeration of $C$ so that the real number constructed in the other answer is computable in the limit ($\Delta^0_2$) if our enumeration is used for $C$. Therefore, at best the answer there is underspecified.

(The quoted material is correct in the claim the original author made, which is just that the number constructed is not computable ($\Delta^0_1$); the underspecification only matters when we ask whether the number is computable in the limit ($\Delta^0_2$).)

Motivation: The enumeration we construct is based on an algorithm that uses the halting problem $\emptyset'$ as an oracle. This algorithm constructs the enumeration in stages by a priority argument. At stage $s$ we have a finite list $T^s_1, T_2, \ldots, T^s_s$ of distinct Turing machines. These may or may not be in $C$. At each step, we will extend the list by one, and we may also replace some of the previous elements of the list by new machines. For each location in the list, the machine in that location will be replaced at most once during the entire construction, and if it is replaced it is replaced by a machine in $C$. If a machine is never replaced, then it is also in $C$. We also ensure that every machine in $C$ is put into the list at some stage and never removed. Therefore, the sequence of lists in the construction converges in the limit to an infinite list $C_1, C_2, C_3, \ldots$ which enumerates $C$. Moreover, the construction will ensure that the function $f(n) = C_n(n)$ is computable from $\emptyset'$, which means that the real number obtained by diagonalizing $f$ is also computable from $\emptyset'$. By standard results, this means the diagonalizing function is computable in the limit.

Construction: We fix an effective enumeration of all Turing machines in the background. At stage $0$, use $\emptyset'$ as an oracle to choose the first machine $T$ in the enumeration for which $T(0)$ is defined and let $T_0^0= T$. At stage $s+1$, we have a list $T^s_0\, \ldots, T^s_s$ of machines which, by induction, all halt on inputs $\{0, \ldots, s\}$. Use $\emptyset'$ to ask whether each of these halts on input $s+1$. For each one that does not, replace it by a new machine not in the list which has the same values on $\{0, \ldots, s\}$ and which returns $0$ for all larger values. We can effectively list infinitely many such machines, so we can effectively pick one not in the list, and we can make sure the elements in the list are distinct. Finally, use $\emptyset'$ as an oracle to find the first machine not in the list which halts on all inputs in $\{0, \ldots, s+1\}$ and append it to the list. This ends stage $s+1$.

Verification: As explained above, the limit of this construction gives an enumeration of some infinite set of Turing machine. We prove the set enumerated is exactly $C$. Any machine in $C$ will halt on every input, so it will eventually be added to the list, because at each stage we add the first remaining machine from the original enumeration that halts on enough inputs, and a machine in $C$ halts on all inputs. Conversely, any machine that remains in the list until the end must halt on every input, or else we would remove it. So the machines that remain in the limit are in $C$.

The other key properties of this construction are that:

• For each $n$, $C_n(n) = T^n_n(n)$. This is because, when we replace a machine in location $n$, we replace it with one that returns the same value on input $n$.

• The function $f(n) = T^n_n(n)$ is computable from $\emptyset'$. This is because the entire construction is computable from $\emptyset'$ (although the limit of the construction is not). So in order to compute $f(n)$ we just simulate the entire construction up to the point where $T^n_n$ is chosen, and then return $T^n_n(n)$.