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?

Improve this question
$\endgroup$
7
  • $\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
    Commented Mar 15, 2012 at 1:59
  • $\begingroup$ @Kaveh What do you mean by "unary"? The linked question considered the decimal representation of $\pi$. $\endgroup$
    – Raphael
    Commented Mar 15, 2012 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
    Commented Mar 15, 2012 at 7:20
  • 1
    $\begingroup$ @Kaveh: We could also have checked for $(01)^n$ without changing the answer. $\endgroup$
    – Raphael
    Commented Mar 15, 2012 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
    Commented Mar 15, 2012 at 13:13

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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'
    Commented Mar 15, 2012 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
    Commented Mar 15, 2012 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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