1

Let $f(n)$ be $$ f(n)=\begin{cases} 1,&\small{\text{if there are digits 1 in the constant $\textit{e}$ $\textit{n}$ times in a row}}\\ 0,&\small{\text{otherwise.}}\\ \end{cases} $$ Is it true that $f(n)$ is computable?

I strongly believe that is not, but I can't even understand how to prove it. What to do?

L. Antz
  • 13
  • 2
  • 2
    This is not a research-level question. It is a basic question in computability theory. Please ask it on math.stackexchange.com and delete it here. – Andrej Bauer May 10 '16 at 18:28
  • I'm sorry, it was mistake, I was confused that there was another site. I will do it later. – L. Antz May 10 '16 at 18:43
  • No problem at all, it's just that it's better for everyone if the questions are properly classified. Now that Joel already answered and you accepted, we might as well leave it as is. – Andrej Bauer May 10 '16 at 20:19
  • I had already answered before your initial comment, Andrej. – Joel David Hamkins May 11 '16 at 14:04

1 Answers1

4

The function is computable. It is either the constant $1$ function, if there are arbitrarily long sequences of consecutive $1$s in the expansion of the number $e$ (and I guess you mean the decimal expansion or the binary expansion), or if there is not, then the function is a simple step function, with value $1$ up to some value $k$, the largest sequence occurring, and $0$ thereafter. All such functions are computable, and therefore, your function is computable.

One shouldn't confuse the fact of the computability of your function with our lack of knowledge about which computable function it is. The argument exhibits a collection of functions, each of which is computable, and a proof that your function is one of those functions. So your function is computable, even if we don't know which one it is.

See also my answer to a related question, where a similar point is made.

  • Note that by contrast the function $f(n)=1$ iff $e$ contains a maximal block of $n$ ones, and $0$ otherwise, is not obviously computable (and I believe is not known to be computable, but is conjectured to be the constant $1$ function). – Noah Schweber May 10 '16 at 18:25
  • Wow, a sudden solution. I thougth that it needed to prove or disprove the existence of such $k$. But it's not necessary, at all. Thanks. – L. Antz May 10 '16 at 18:31