HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is a function looking for subsequences of digits of $\pi$ computable?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
computabledigitsfunctionlookingforsubsequences

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#401, answer score: 3

Revisions (0)

No revisions yet.