1
$\begingroup$

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$?

1 Answers 1

4

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?