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.

Let $f:\mathbb{N}\to\mathbb{N}$ be given by $f(n)=1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s, and $f(n)=0$ otherwise.

How would you go about showing such a function is primitive recursive?

I suppose you should be able to construct it out of other p.r. functions, via composition or the basic recursion scheme that the family of p.r. functions is closed under (I don't know if such an algorithm has a name). However, I do not know how to deal with the decimal expansion of anything (much less an irrational) as something that would come from p.r. functions. Particularly because if it's irrational, you'd have to express it as an infinite series (i.e. an infinite number of sums).

share|improve this question
1  
Well, notice that if the decimal expansion of $\pi$ contains a string of $n$ consecutive "5"s, then it certainly contains a string of $m$ consecutive "5"s for any $m < n$. So $f$ is either the constant $1$ function, or is $0$ after a certain point. Either way, $f$ is (the graph of) a primitive recursive function, even though we don't know which! –  Zhen Lin Aug 16 '12 at 15:20

1 Answer 1

up vote 11 down vote accepted

It's a trick question -- it is easy to show that your function must have a primitive recursive definition, but very hard to say with certainty what that primitive recursive definition is.

Either the decimal expansion of $\pi$ contains arbitrary long sequences of consecutive 5's, and in that case $f(n)$ is the function that always returns $1$. That is obviously primitive recursive. --

Or the decimal expansion of $\pi$ contains $N$ consecutive 5's somewhere, but never contains $N+1$ consecutive 5's, for some finite $N$. In that case $$ f(n)=\begin{cases}1 & \text{if }n\le N \\ 0\ &\text{otherwise} \end{cases}$$ which is also obviously primitive recursive.

The lesson to take home is that "is primitive recursive" is a property only on the contents of the abstract set $\{(x,y)\mid f(x)=y\}$, and does not depend on how you describe or define that contents.


If this feels too fuzzy, consider this simpler example: Define the number $K$ to be $42$ if the Riemann Hypothesis is true and $57$ otherwise. It is extremely difficult to prove stuff about $K$ explicitly, but we can say with absolute certainty that it's an integer, is less than $100$ and is not a perfect square. To prove these things we don't need to know whether RH is true; it suffices to show that no matter whether it is or not, the property we're after will be true. It's the same with "is a primitive recursive function".

share|improve this answer
    
Very nice answer. –  Brian M. Scott Aug 16 '12 at 19:31
    
I love these kinds of proofs. +1 to the questioner as I have already given your answer a +1. –  Cocopuffs Aug 16 '12 at 20:55
    
Very nice indeed. –  FPP Aug 17 '12 at 16:02

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.