# Computing real numbers with Turing Machines

Consider the following decision problem:

Given a two integers $$n$$ and $$k$$, decide whether $$k=\lfloor n\pi\rfloor$$

Question: Is this problem known to be in $$P$$?

Although this may look like a stupid question, I believe it is not. The reason is that the classical model of computation is inherently discrete, and it is not clear what is the complexity of computing functions such as $$n\mapsto \lfloor n\pi\rfloor$$. What I can prove so far is the following:

Claim: There exists an algorithm that computes in time $$n^{O(1)}$$ an rational number $$k$$ such that $$|k-n\pi|<1$$.

Proof. The algorithm is based on the Leibniz formula: $$\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\dots$$ It is not difficult to show that we can compute the sum of the first $$n$$ terms in time $$poly(n)$$ to get an approximation $$\hat{\pi}$$ of $$\pi$$ such that $$|\pi-\hat{\pi}|=O(1/n)$$. Then, the algorithm outputs $$k:=n\hat{\pi}$$.

However, this does not really answer the question above. It might be for example that for any constant $$\gamma$$, there exists an integer $$n_\gamma$$ for which $$n_\gamma\pi-\lfloor n_\gamma\pi\rfloor<\frac{1}{n^\gamma}$$. If this is true, then whatever polynomial number of terms the algorithm of the claim would calculate, it would fail to compute $$\lfloor n\pi\rfloor$$ for at least one input integer $$n$$.

I'm interested in any interesting thoughts or references related to this type of questions.

• $n^{O(1)}$ is not polynomial time, but exponential, as the input has length $\log n$. But you can compute $\lfloor n\pi\rfloor$ in time $O(M(\log n)\log\log n)=\log n\,(\log\log n)^{O(1)}$ (where $M(m)$ is the compexity of $m$-bit integer multiplication). See e.g. mathoverflow.net/questions/433675/… . Nov 17, 2022 at 15:26
• In particular, the scenario in your penultimate paragraph cannot happen, because $\pi$ has finite irrationality measure. Nov 17, 2022 at 15:29