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.

Possible Duplicate:
Show $f$ is primitive recursive, where $f(n) = 1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s

$$L = \{i\mid f(i)=1\}$$ $f(i)$ equals $1$ if there is a sequence of at least $i$ consecutive $5$s in the decimal expansion of $\pi$, and $0$ otherwise.

Is there a total Turing Machine that can represent that language for any $i$?

share|improve this question
add comment

marked as duplicate by Carl Mummert, Thomas, Martin Sleziak, Norbert, tomasz Oct 9 '12 at 20:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 4 down vote accepted

Since this is homework, I'll just drop hints:

  • If there's a run of $n$ fives in $\langle\pi\rangle$, the decimal expansion of $\pi$, there are also runs of $1,2,\ldots,n-1$ fives.
  • We don't know the entire sequence of digits in $\langle\pi\rangle$. But there are two cases to consider: Either $\langle\pi\rangle$ has unbounded runs of fives, or it doesn't, and the maximum run has length $n$. (we don't know precisely which is the case). Can you devise a decider (a TM that decides yes or no for every input) for each case?
share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.