Assume generating means that for all $k$ there exists $N_k$ such that after $N_k$ steps the $k$th cell on the tape consists of the $k$th digit of $\pi$'s binary expansion and will stay there forever.

Can such a machine exist? can it not?


Is this true for every irrational number?

So this is true for $\pi$ since there exists a Turing machine to calculate the $k$th digit of $pi$ so we can construct a machine that calls the prior machine to calculate digit by digit.

But this can not be true for all irrational numbers since there are uncountably many irrational numbers and only countably many turing machines.

From this we can conclude that $\pi$ is among a special countable set of irrational numbers, call it $G$, that are generatable in the sense above.

Do we know what is the set $G = \{ g \in \mathbb{R} \setminus \mathbb{Q} : g$ is generatable $\}$ in a mathematical sense or a more informative way? We know $\pi \in G$ and we know $G$ is countable. Is there more to the picture?

  • $\begingroup$ There is an algorithm to compute the digits of $\pi$. This algorithm can be implemented on a Turing machine. $\endgroup$ – Hendrik Jan Jun 17 at 9:13
  • $\begingroup$ Thanks let me expand the question please, Is this true for every irrational number? $\endgroup$ – Oren Jun 17 at 9:15
  • $\begingroup$ It is a question of computability, whether there exists an algorithm to find the digits. There exist uncomputable numbers. $\endgroup$ – Hendrik Jan Jun 17 at 9:18
  • 3
    $\begingroup$ It was already asked here: cs.stackexchange.com/questions/91847/… $\endgroup$ – Albert Hendriks Jun 17 at 9:52
  • 1
    $\begingroup$ @reinierpost That is not true, that question is not about finite numbers but about irrational numbers. Read further than the title. $\endgroup$ – Albert Hendriks Jun 17 at 13:28

Browse other questions tagged or ask your own question.