1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Commented May 10, 2016 at 18:28
  • $\begingroup$ I'm sorry, it was mistake, I was confused that there was another site. I will do it later. $\endgroup$
    – L. Antz
    Commented May 10, 2016 at 18:43
  • $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Commented May 10, 2016 at 20:19
  • $\begingroup$ I had already answered before your initial comment, Andrej. $\endgroup$
    – Joel David Hamkins
    Commented May 11, 2016 at 14:04

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Noah Schweber
    Commented May 10, 2016 at 18:25
  • $\begingroup$ 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. $\endgroup$
    – L. Antz
    Commented May 10, 2016 at 18:31

Not the answer you're looking for? Browse other questions tagged .