15
$\begingroup$

When I first learned about computable numbers, I misunderstood the (informal) definition, thinking it was this: a number $x$ is computable if there exists a turing machine that outputs a sequence of numbers that converges to $x$. The real definition is: a number $x$ is computable if there exists a turing machine $M$ such that for every $n > 0$, $M$, when ran with $n$ as input, terminates and outputs the first $n$ digits of $x$. The real definition is clearly stronger, and it makes the distinction that you don't only have to be able to compute $x$, but to know how close you are to it.

Clearly there are only countable many numbers that satisfy this weaker definition, but I haven't been able to find any examples of numbers that don't satisfy my definition. All of the examples of uncomputable numbers I know use the halting problem in some way, and they are uncomputable because you can't know for sure how close you are to the number. For example, you can enumerate all of the turing machines and define $x=0.h_1h_2h_3...$ where $h_i$ encodes whether the $i$th turing machine halts. But this number does satisfy the weaker definition: create a turing machine that, in the $n$th iteration simulates the first $n$ turing machines to $n$ steps and output these $n$ digits. If $m$ is the longest finite running time in the first $100$ turing machines, then after $m$ iterations, the first $100$ digits it outputs will be right. You simply can't know when they are.

A similar method works for every uncomputable number I've heard of, since usually you actually can compute them, you just can't know how close you are to them.

$\textbf {question:}$ Can anyone give me an example of an uncomputable number that is also not "weakly computable" by my definition?

$\endgroup$
3
  • 4
    $\begingroup$ Awkwardly, even if I promise you that my Turing machine outputs a sequence converging to $x$, then running my Turing machine will never tell you anything about $x$ that you didn't already know. No matter how big the input $n$ is, it's possible that the sequence "hasn't started converging yet" and the outputs it's giving are completely irrelevant. $\endgroup$ Sep 14 at 15:38
  • 2
    $\begingroup$ This question is like asking for a non-describable number. The very nature of the thing makes it hard to give a specific example. $\endgroup$
    – Dan
    Sep 14 at 19:07
  • 2
    $\begingroup$ $\pi ,$ but backwards. $\endgroup$
    – Nat
    Sep 15 at 2:29

2 Answers 2

12
$\begingroup$

Let me start by shifting to a slightly tamer context: sets of naturals (or infinite binary sequences) instead of reals. This lets us avoid issues of non-unique expansions, while still having a meaningful notion of convergence ($2^\mathbb{N}$ is basically just the Cantor set in disguise). Ultimately the picture will be the same, but this makes things a bit easier.

Modulo this perspective shift, you're esssentially asking about the limit computable sets. It turns out (due to Schoenfield) that a set is limit computable iff it is computable relative to the halting problem. This (+ some classical results) gives us many natural examples of sets that cannot be computed in your sense, the simplest being $$\mathsf{Tot}=\{e:\forall n, \varphi_e(n)\downarrow\}$$ (here "$\varphi_e$" is the $e$th partial computable function in some standard enumeration, and "$\downarrow$" means "is defined"). This set has Turing degree $\emptyset''$, which is strictly more complicated than the halting problem.

Moving things back into the $\mathbb{R}$eal setting, we would consider the sum $$\sum_{i\in\mathbb{N}}2^{-\mathsf{tot}(i)}$$ where $\mathsf{tot}(-)$ is the characteristic function of the set $\mathsf{Tot}$ defined above.

$\endgroup$
9
$\begingroup$

We can always diagonalize: let $$ x = 0.x_1x_2x_3 \dots $$ where, if the $i^{\text{th}}$ Turing machine, when we interpret its outputs as elements of $[0,1]$ in our favorite way, happens to generate a sequence converging to $b = 0.b_1b_2b_3\dots$, we define $x_i = 1 - b_i$. If the $i^{\text{th}}$ Turing machine doesn't always halt with input $n \in \mathbb N$, or if it halts but the sequence it outputs doesn't converge, then we define $x_i = 0$ for concreteness.

Then of course no Turing machine can output a sequence converging to $x$, because for every Turing machine, we've fixed a bit of it to spoil that convergence.

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