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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to think of an example of a real number $R$ such that the map $n \mapsto R[n]$, where $R[n]$ is the $n$th digit of the decimal representation of $R$, is not recursive.

So I was thinking to take an irrational number such as $\pi$, or $e$. Then can we argue by Church's thesis? What better examples are there?

share|cite|improve this question
Most numbers are like this, as there are only countably many algorithms and uncountably many reals. But exhibiting one is very difficult. Most reasonable ways of describing a number provide an algorithm. – Ross Millikan Mar 6 '13 at 0:41
In computability, the distinction between reals (in $[0,1]$) and subsets of $\mathbb{N}$ is (justifiably) blurred. All you're really asking for is a non-computable set. – Quinn Culver Mar 7 '13 at 1:03
up vote 4 down vote accepted

$\pi$ and $e$ won't do it; they are eminently recursive, because we have algorithms that calculate the $n$th digit of each.

Any such number must be very weird, and (obviously) its exact numerical value must be unknown. Chaitin's constant is an example. But here is an even simpler example: Let $M$ be an enumeration of turing machines. Let $R$ be such that $R[n]$ is 1 if $M(n)$ halts on all inputs, and 0 if there is some input on which $M(n)$ does not halt. Then $R$ is clearly non recursive; if $R$ were recursive, the halting problem would be solvable. The Chaitin construction is similar. Chaitin's constant $\Omega$ is a number which in a certain sense represents the probability that a randomly-selected turing machine will halt.

share|cite|improve this answer
Can you give some more examples of something that I could better see it? Also, can you please justify why your constant is an example. Thanks – Buddy Holly Mar 6 '13 at 0:36

Your Answer


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.