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!

@KennyLau I know how to solve my problem X in other ways. Using this turing machine counter would be another solution. I just don't know if such a turing machine can be created. I can delete the first sentence of my question if it's a problem. — T.Poe, Dec 27 '17 at 08:04
It rejects if there is input 9, 99 etc. But yes, if it accepted this, it would be it. — T.Poe, Dec 27 '17 at 08:23

score 0 · Accepted Answer · answered Dec 27 '17 at 09:48

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)$

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

1 Answers1