[Math] Turing machines that compute $\pi$

arithmeticcomputabilityrecursive algorithms

For each $K > 0$ there is a brut force Turing machine $\pi_K$ that "computes" the first $K$ digits of $\pi$ starting on the blank tape (all $b$s) with

  • $K+1$ states $S \in \mathsf{S} = \{0,1,\dots ,K\} = [K]$
  • $11$ symbols $s \in \mathsf{s} = \{0,1,\dots ,9,b\}$
  • $2$ directions $r \in \mathsf{r} = \{L,R\} $

and functions

  • $\Sigma: [K-1] \times \{b\} \rightarrow \mathsf{S}$ (next state)

  • $\sigma: [K-1] \times \{b\} \rightarrow \mathsf{s}$ (write symbol)

  • $\rho: [K-1] \times \{b\} \rightarrow \mathsf{r}$ (go to)

State $0$ is implicitly assumed to be the initial state, state $K$ is implicitly assumed to be the halting state (for which $\Sigma, \sigma, \rho$ are not defined anymore).

$\pi_K$ is explicitly given by:

$\Sigma(k,b) = k+1$

$\rho(k,b) \equiv R$

$\sigma(0,b) = \mathbf{1}$

$\sigma(1,b) = \mathbf{4}$

$\sigma(2,b) = \mathbf{1}$

$\sigma(3,b) = \mathbf{5}$

$\dots$

$\sigma(K-1,b) = \pi(K)$

with $\pi(k)=$ the $k$-th digit of $\pi$ in decimal representation.

Since $\pi$ is a computable number there are Turing machines that build up $\pi$ digit by digit endlessly on the initially blank tape. (Left to the starting head position any intermediate data may be written at any time.)

These $\pi$-machines can be compared in two ways:

  • by their numbers of states (necessarily finite)

  • by their numbers of steps needed to compute the $k+1$-th digit after having computed the $k$-th digit (in Big-O notation)

Note that for $\lim_{K\rightarrow \infty}\pi_K$ the number of states tends to $\infty$, but the number of steps is constantly $\mathcal{O}(1)$.

I wonder what the best known $\pi$-machine is with respect to

  • number of states

  • number of steps

  • number of states and number of steps adequately combined.

Best Answer

This is only from the top of my head, but

  • number of steps

    Your trivial turing machines that compute PI obviously win this one, only needing the minimal one step to write down the digit

  • number of states

    For any big $ K $ this will be the shortest possible algorithm to calculate the next digit of $ \pi $, because the number of states is independent of $ K $. I can't imagine anyone willing to optimize turing machine graphs, but it exists in theory.

  • number of states and number of steps adequately combined

    This clearly depends on what do you mean adequately. As a rule of thumb in programming you can always trade of speed (number of steps) for memory (number of states).

    I don't know what the computational complexity of the best possible $ \pi $ algorithm out there, but it's probably at least O(n) for a digit (given how slow it is to compute it) And you need extra steps to manage memory too (which also has a greater than O(1) complexity). So if your "adequate" combination is simply $ \alpha * numberOfStates + \beta * numberOfSteps $ , computing the next digit is clearly loses to storing it as a state.

Despite that, the trivial ($ K + 1 $ states) turing machine isn't the best solution. If you want to minimize the number of states, while not allowing the number of Steps to grow with $ K $, you essentially searching for the best compression of $ \pi $ for a given overhead.

There are many compression algorithms available, LW77 for example uses a fixed size window to look back, so the number of steps required by the algorithm can be as low as $ O(K * M) $, $ M $ being the window's size. the number of states is still $ O(K) $ but it can be less than $ K + 1 $, due to the compression of data.

Some very fast very trivial compression can probably beat the algorithmic version of computing $ \pi $ in the number of states too, for some values of $ K $, because compiting $ \pi $ is difficult, and some compression algorithm can have really few states.

Related Question