0

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?

MJD
  • 65,394
  • 39
  • 298
  • 580
Buddy Holly
  • 1,189
  • 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 06 '13 at 00: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 07 '13 at 01:03

1 Answers1

4

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

MJD
  • 65,394
  • 39
  • 298
  • 580
  • 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 06 '13 at 00:36