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.

$\endgroup$
  • 9
    $\begingroup$ Have you seen Chaitin's constant before? $\endgroup$ – Srivatsan Jan 21 '12 at 18:18
  • 6
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jan 21 '12 at 18:24
  • 5
    $\begingroup$ 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. $\endgroup$ – Jonas Kibelbek Jan 21 '12 at 18:30
  • 1
    $\begingroup$ @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. $\endgroup$ – John Jan 21 '12 at 19:35
  • 1
    $\begingroup$ @Holowitz The latter, a sequence of (rational) numbers. What's computable finite time? $\endgroup$ – John Jan 21 '12 at 22:27
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – John Feb 19 '12 at 15:43
  • $\begingroup$ 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? $\endgroup$ – Kyle Strand Aug 26 '15 at 21:20
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – John Jan 21 '12 at 23:05
  • 2
    $\begingroup$ 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". $\endgroup$ – Quinn Culver Jan 22 '12 at 2:54
  • 1
    $\begingroup$ @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). $\endgroup$ – John Jan 22 '12 at 11:10
  • 2
    $\begingroup$ 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. $\endgroup$ – Carl Mummert Feb 10 '12 at 13:47
  • 1
    $\begingroup$ @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. $\endgroup$ – Carl Mummert Feb 12 '12 at 23:03
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Carl Mummert Feb 10 '12 at 13:54
0
$\begingroup$

A concrete example relying on Turing Machines and Cauchy suites.

A TM computing a real number $r$ as limit of a computable sequence is such that for any input $n$ it computes the value $u(n)$ of a Cauchy suite converging to $r$, where the values of $u(n)$ are decimal numbers.

Consider a Cauchy suite $u: \mathbb N → [0,1[$ such that there exists a TM such that for any input $n$ the output is a finite sequence of digits which represents the values of the the digits of $u(n)$ at the right of "$0,$". For any $n$ the TM computes $u(n)$, let's say this TM computes $u$ and that such a Cauchy suite is computable.
Now consider the set of all such computable Cauchy suites over $[0,1[$. Consider an enumeration of those suites : each suite is computable by a TM, let order the suites by their Kolmogorov complexity (the shortest TM computing such a Cauchy suite).
Each suite converges to a real number in $[0,1[$ whose digits at the right of "$0,$" are infinite sequences of digits, or finite sequences, in this case we complete with "$0$" to obtain infinite sequences. The previous enumeration is an enumeration of all those infinite sequences. So we can use the Cantor's diagonal to define a new infinite sequence which is different from all previous ones, that is, this sequence represents the digits of a real number in $[0,1[$ such that no computable Cauchy suite converges to it. Thus, there exists no TM such that the output, for any input $n$, will ever reach this real number with a given precision $\epsilon>0$ ($\epsilon$ depending on the TM).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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