9
$\begingroup$

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.

  • 9
    Have you seen [Chaitin's constant](http://en.wikipedia.org/wiki/Chaitin's_constant) before?2012-01-21
  • 6
    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.2012-01-21
  • 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.2012-01-21
  • 0
    Related to http://math.stackexchange.com/questions/58036/are-some-real-numbers-uncomputable/2012-01-21
  • 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.2012-01-21
  • 0
    @Srivatsan Please see my previous comment.2012-01-21
  • 0
    @AsafKaragila You're right, I'll edit the question. The question to pick on is still non-trivial and I have the feeling that this is usually formulated in set-theoretical term.2012-01-21
  • 0
    @John: Indeed many things are formulated in set theoretical terms; and furthermore many fields nowadays assume the axiom of choice all across the board. However your question does not seem to me as related to the axiom of choice. With your edit, I will remove the tag as well,if you don't mind.2012-01-21
  • 0
    @John: It's a nice question, and I'm interested to see what answers show up. Maybe you should change the title to something like "Example of a number that is not the limit of any computable sequence," since that may describe the question better to experts. (I am not one.)2012-01-21
  • 0
    Can you clarify more clearly how you interpret the output of your algorithm? Is it a sequence of 0's and 1's interpreted as a decimal number, or can it be any series of fractions and integers 1/7-377+1/89-1+88.. ? I think this question hinges on whether the algorithm converge to any precision in computable finite time2012-01-21
  • 1
    @Holowitz The latter, a sequence of (rational) numbers. What's computable finite time?2012-01-21
  • 0
    It is interesting that you can find an algorithm which generates all the rationals (possibly with repetition), and any real number is a cluster point of this sequence....2012-01-21

5 Answers 5

4

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

  • 0
    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.2012-02-19
  • 0
    I am unfamiliar with all of the things you linked to, so I don't yet fully understand this answer. I'd like some intuition about what's meant by "arithmetically definable," though, if possible. Can you, for instance, determine the first several decimal-place digits of $\mathrm{Tot}$? The 30th? The $n$th?2015-08-26
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

  • 0
    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.2012-01-21
  • 2
    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".2012-01-22
  • 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).2012-01-22
  • 0
    @John You said you weren't interested merely in a proof of existence, since that's trivial. Presumably you were saying that since you know the cardinality of 'computable' numbers is countable, there must be some. But the way that fact is proven is by a (non-effective) diagonalization, which essentially just does the same thing as in the paper by Brener. The point is that you're really not getting a concrete example; you're only getting a concrete example based on the assumption that you have (access to) an enumeration of all 'computable' numbers. Such an enumeration is not very concrete.2012-02-05
  • 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.2012-02-10
  • 0
    @CarlMummert I don't have the necessary background to do so but I can delete the answer.2012-02-10
  • 0
    @Mahmud: I don't think it's necessary to delete it; you could just add a note to say that it covers the usual definition of a computable real number but not the more general one from the question. The answer itself is still relevant.2012-02-10
  • 0
    @CarlMummert The paper Mahmud cites does actually diagonalize out of the $\Delta^{0}_{2}$ reals (which he calls "approachable") in Section 5. That's the diagonalization I was referring to. (For some reason I just looked at the paper and assumed that was the result from it that Mahmud was citing.)2012-02-12
  • 0
    @CarlMummert The point is that if Mahmud just changed his answer to quote to section 5 (instead of 2.3), he'd be correct. As I indicate in my answer, I think this number is $\Pi^{0}_{3}$.2012-02-12
  • 0
    @Quinn Culver: thanks for clarifying. I had thought about the complexity of the real that is generated by the answer literally quoted above. My answer shows that this real may be $\Delta^0_2$ if the right enumeration of total machines is used; this is what I was thinking about when I obtained that construction, because I wondered whether the construction above might accidentally give an example.2012-02-12
  • 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.2012-02-12
2

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

  • 0
    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.2012-02-10
-4

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

  • 0
    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?2012-01-21
  • 0
    Why do you need to check it?2012-01-21
  • 1
    I think this number *is* computable according to John's definition.2012-01-22
  • 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.2012-02-05
  • 0
    This number is certainly computable in the limit, which is what the question asked about. The $n$th element in an approximating sequence will ask whether each algorithm with index $\leq n$ has halted in $\leq n$ steps.2012-02-09
  • 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.2012-02-15