Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 asking for a concrete example: To pick one of those numbers by defining it.

My feeling is that this is possible.

share|improve this question
9  
Have you seen Chaitin's constant before? –  Srivatsan Jan 21 '12 at 18:18
5  
The uncountability of the real numbers does not follow from the axiom of choice. It follows from Cantor's theorem, which is true even without the axiom of choice. Simply by the fact that the number of computable elements is countable you have a proof of the existence of such number. –  Asaf Karagila Jan 21 '12 at 18:24
5  
I believe there's an important difference between the definition of computability of $r$ you give above-- that there's an algorithm generating a sequence with $r$ as its limit-- and the standard definition-- there is an algorithm that, given $n$, returns a number within distance $1/n$ of $r$. There is an algorithm for a sequence of numbers that converge to Chaitin's constant-- at step $n$, just run the first $n$ programs for $n$ steps to see if they halt. (We just don't know how quickly this sequence converges.) But there is no algorithm to obtain the first $n$ digits of Chaitin's constant. –  Jonas Kibelbek Jan 21 '12 at 18:30
1  
@Jonas: I didn't know about Chaintin's constant - and yes, my definition is different, so it was unfortunate that I called my definition computable. My questions are referring to my definition, not the common one. It's an interesting difference though and I didn't know about it either. –  John Jan 21 '12 at 19:35
1  
@Holowitz The latter, a sequence of (rational) numbers. What's computable finite time? –  John Jan 21 '12 at 22:27

5 Answers 5

up vote 4 down vote accepted

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}$.

share|improve this answer
    
Thanks for your efforts of mapping my definition to the classical terminology and putting my question in context. I didn't now about the arithmetical hierarchy either. I need to think about this more, but I can already say that this has been most helpful. –  John Feb 19 '12 at 15:43

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

share|improve this answer
    
My definition for "computable" differs from the common one, as discussed in the comments of the question - but the construction appears to work in both cases. It's just the classical construction for a real number not in a given countable subset of numbers in [0,1]. So that was a lot easier than I thought. –  John Jan 21 '12 at 23:05
1  
Given that you, @John, said "So what I'm interested in is not a proof for existence - that one is trivial. I asking for a concrete example: To pick one of those numbers by defining it.", I don't think this answer is appropriate. The number given isn't really 'defined' (at least not in the sense I think you meant) since the set $C_{b}$ cannot be attained effectively. Thus this proof is no different than just saying, "the set of all computable numbers is countable, so there must be at least one noncomputable number". –  Quinn Culver Jan 22 '12 at 2:54
1  
@QuinnCulver I don't meant to imply any "effectiveness" in obtaining the number - in fact I don't even know how what this should mean precisely and I expected the solution to be more difficult than this. It is still different than to simply point out a set being non-empty. There are some cases where solutions to a problem exist but it is impossible to pick one (often because the solution depends on the axiom of choice). –  John Jan 22 '12 at 11:10
2  
This answer does not solve the stated problem. The number generated by diagonalization is definitely not computable ($\Delta^0_1$) but no proof is given that it is not computable in the limit ($\Delta^0_2$). The other examples are certainly $\Delta^0_1$. Moreover, I give in another answer an enumeration of $C$ such that if that enumeration is used then the diagonal number produced in this answer is $\Delta^0_2$, which means that at best there might be some enumeration of $C$ for which the diagonal number is not $\Delta^0_2$, but the existence of such an enumeration is not obvious. –  Carl Mummert Feb 10 '12 at 13:47
1  
@Quinn Culver: by changing my proof to use $\emptyset''$ and replacing "$\phi_e$ halts on input $n$" with "$\lim_{m \to \infty} \phi_e(n,m)$ exists", we can get a $\Delta^0_3$ real that diagonalizes against the $\Delta^0_2$ reals. This is informally some sort of relativization of the entire proof to $0''$; the same thing will work for $\Delta^0_n$ for $n > 1$, of course. –  Carl Mummert Feb 12 '12 at 23:03

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)$.

share|improve this answer
    
By the way, the characteristic function of the $\Pi^0_2$ set of total Turing machines (relative to any admissible enumeration) is an example of a function that is not $\Delta^0_2$, which is an example of the sort that the problem asks for. –  Carl Mummert Feb 10 '12 at 13:54

@Quinn Culver, C is not computable according to John's definition: it is not the limit of a computable sequence.

@John, the response to your question is YES, it is possible to give an a "concrete" definition of such a real. An example based on TMs is given the appendix of [1]. It is roughly the same as C, the difficult part is the encoding of the TMs but it is only technical.

@Holowitz, your C is clearly not the limit of a computable sequence, I don't see what is matter of philosophy here.

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

share|improve this answer
1  
Here is why $\mathbf{C}$ is the limit of a computable sequence. Set $x_0=0$. Run all TMs, and, given $x_k$, whenever you see halting of the $i$th machine (for $i\leq k$ and in $\leq k$ steps), set $x_{k+1}$ to be the same as $x_{k}$ except that its $i$th binary digit is as @Holowitz described. –  Quinn Culver Feb 5 '12 at 16:38
    
And notice that the difference between the example in the paper you cited is that it started with a non-computable numbering (of all the 'approachable' numbers; notice that 'approachable' there is the same as John's 'computable'). However, @Holowitz tried to diagonalize out of the computable numbering of all algorithms. –  Quinn Culver Feb 5 '12 at 19:39
    
Quinn Culver's construction is correct. Note that just because a real is the limit of a computable sequence does not mean the real is itself computable in the ordinary ($\Delta^0_1$) sense. For example, the binary expansion of the halting set $K$ is computable in the limit, using the same construction. –  Carl Mummert Feb 9 '12 at 15:55

Enumerate all algorithms $A_i$ (algorithms are finite strings of symbols). Define $a_i=0$ if algorithm $A_i$ outputs nothing or the output diverges, else let $a_i$ differ from the number $A_i$ outputs converges to in the n'th binary decimal place.

Then you have a $C=0.a_1 a_2a_3...$

share|improve this answer
    
Can't find a flaw in your proof, seems right to me. I don't understand your reference to philosophy though. How can a sequence-producing algorithm not do either crash, diverge on converge? Also, how's your answer not having the same "problem" (which I don't think is a problem) as similar construction of Qiaochu you complained about? –  John Jan 21 '12 at 22:11
    
Why do you need to check it? –  John Jan 21 '12 at 22:39
1  
I think this number is computable according to John's definition. –  Quinn Culver Jan 22 '12 at 2:07
1  
Well that's a nice thing to say! Thank you so much. But seriously, read my comment to @Nico's answer and then, based on that, explain to me why your number is incomputable. –  Quinn Culver Feb 5 '12 at 17:02
1  
By the way, I'm disappointed that someone removed @Holowitz's comment calling me a 'moron'. I realize there's some kind of etiquette to be followed here on math.SE, but that was pretty funny. –  Quinn Culver Feb 15 '12 at 13:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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