Turing machines that compute $\pi$ 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.

 A: 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.
