Is it possible to make a turing machine counter for decimal numbers?

Question

I'm solving a complex task using turing machines. To solve it, my idea was to use a turing machine, that would count decimal numbers, one digit per one place on the tape (# 1 #, # 2 #, ..., # 9 9 #, ...) . But as my knowledge of turing machines is limited, I can't figure out how it could do it or if it's even possible.

So my question is: Is it possible? If so, could you provide just a basic idea of how it'd work? Thanks!

Answer 1

You can describe a generic TM counter $M_b = (Q, \Sigma, \Gamma, \delta, q_\text{goto end}, B, F)$ for a base $b \geq 1$ with

• $\Sigma = \{0, \ldots, b-1\}$ for $b \geq 2$ and $\Sigma = \{1\}$ for $b = 1$
• $\Gamma = \Sigma \cup \{B\}$
• $Q = \{q_\text{goto end}, q_\text{inc}, q_\text{done}\}$
• $F = \{q_\text{done}\}$

• and $\delta$ as follows

  • Go to the right end
    $\forall a\in\Sigma: \delta(q_\text{goto end}, a) = (q_\text{goto end}, a, R)$
    $\delta(q_\text{goto end}, B) = (q_\text{inc}, B, L)$
    
  • Increment the digit
    
    • For $b \geq 2$:
      $\forall d\in\Sigma\setminus\{b-1\}: \delta(q_\text{inc}, d) = (q_\text{done}, d+1, N)$
      $\delta(q_\text{inc}, b-1) = (q_\text{inc}, 0, L)$
      
    • For $b = 1$:
      $\delta(q_\text{inc}, 1) = (q_\text{inc}, 1, L)$
      
    • For both, add a new digit in case we reached the left end:
      $\delta(q_\text{inc}, B) = (q_\text{done}, 1, N)$