Take the 2-minute tour ×
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.

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|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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.