11
$\begingroup$

How can it be decidable whether $\pi$ has some sequence of digits? inspired me to ask whether the following innocent-looking variation is computable:

$$f(n) = \begin{cases} 1 & \text{if \(\bar n\) occurs in the decimal representation of \(\pi\)} \\ 0 & \text{otherwise} \\ \end{cases}$$

where $\bar n$ is the decimal representation of $n$ with no leading zeroes.

If the decimal expansion of $\pi$ contains all finite digit sequences (let's call this a universal number (in base 10)), then $f$ is the constant $1$. But this is an open mathematical question. If $\pi$ is not universal, does this mean that $f$ is uncomputable?

$\endgroup$
  • $\begingroup$ the trick for the other problem works because it is unary, that trick will not work for checking binary strings. But it doesn't mean it is not possible in some other way. $\endgroup$ – Kaveh Mar 15 '12 at 1:59
  • $\begingroup$ @Kaveh What do you mean by "unary"? The linked question considered the decimal representation of $\pi$. $\endgroup$ – Raphael Mar 15 '12 at 7:14
  • $\begingroup$ This is one way to render the $\pi$-example uncomputable. The other way is to give a real number as input. I don't have a proof handy, though. $\endgroup$ – Raphael Mar 15 '12 at 7:20
  • 1
    $\begingroup$ @Kaveh: We could also have checked for $(01)^n$ without changing the answer. $\endgroup$ – Raphael Mar 15 '12 at 7:39
  • 1
    $\begingroup$ @Raphael, you can think of it as essentially unary also. (The important thing is the structure of possible strings to check w.r.t. prefix relation.) $\endgroup$ – Kaveh Mar 15 '12 at 13:13
3
$\begingroup$

Note that $f$ can be the constant $1$ even if $\pi$ is not a normal number. (In French we say if $f$ is constant that $\pi$ is a nombre univers. I don't know the corresponding term in English)

For what it's worth: it could be, in the following way:

Proving $f$ is computable would not necessarily imply the resolution of the open question whether $f$ is constant or not. For example you can build $g$ that is computable but such that the constantness of $g$ is equivalent to Goldbach's conjecture.

Of course that does not even begin to answer your question, but it's likely open to me.

$\endgroup$
  • $\begingroup$ Right, I did mean nombre univers, in fact. So $f$ could be computable without being constant. I'm pretty sure there's a simpler way to show this. Could you explain a little more how $f$ may or may not be computable, at the level of computability theory 101? $\endgroup$ – Gilles 'SO- stop being evil' Mar 15 '12 at 15:16
  • $\begingroup$ Well I wanted to answer the question "Given that $[f?=1$ is a difficult question$]$, does $f≠1$ implies that $P(f)$?" and my answer is "Why not? At least $¬P(f)$ does not imply that $[f?=1$ is a trivial question$]$" $\endgroup$ – jmad Mar 15 '12 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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