# Number of Turing machines

-What is the number of Turing machines with with the state set $\{Q-\text{start}, Q2, Q3, Q4, Q5, Q6, Q-\text{accept}, Q-\text{reject}\}$, input alphabet $\{0,1\}$ and tape alphabet $\{0,1,\text{x},\text{U}\}$ where $\text{U}$ is the blank symbol? The start, accept and reject states are the ones with the appropriate names. Show your work.

• It looks clear enough to me. The question asks how many possible ways there are to fill out the transition table given this number of states and alphabet sizes. Commented Sep 4, 2017 at 19:07
• You mean going right and left in tape? Commented Sep 4, 2017 at 19:12
• I mean the entire transition table, and everything in it. Commented Sep 4, 2017 at 19:17
• Nice question. Endorsed. I edited your text to $\LaTeX$ify the math. Cheers! Commented Sep 4, 2017 at 19:26
• could you show me an example please ? Commented Sep 4, 2017 at 19:26

Assuming the quadruple formalization of Turing-machines, every transition is of the form $<Q_i, S_j, A_{ij}, Q_{ij}>$: 'If you arer in state $Q_i$ and read symbol $S_j$, perform action $A_{ij}$ (which is either to move left or right or print a symbol), and go to new state $Q_{ij}$:

you have $6$ choices for $Q_i$ (the $Q_{Accept}$ and $Q_{Reject}$ do not have any outgoing transitions)

You have $4$ choices for the symbol you are reading

You have $6$ choices for the action: move left, move right, or print any of the $4$ symbols

You have $8$ choices for the new state

So: for each of the $6\cdot 4 = 24$ entries in the transition-table, you have $6\cdot8=48$ possibilities, giving you $48^{24}$ possible Turing-machines using the quadruple formalization.

Assuming the quintuple formalization of Turing-machines, every transition is of the form $<Q_i, S_j, S_{ij}, A_{ij}, Q_{ij}>$: 'If you are in state $Q_i$ and read symbol $S_j$, print out symbol $S_{ij}$, perform action $A_{ij}$ (move left or right), and go to new state $Q_{ij}$:

you have $6$ choices for $Q_i$ (the $Q_{Accept}$ and $Q_{Reject}$ do not have any outgoing transitions)

You have $4$ choices for the symbols you are reading

You have $4$ choices for the symbol you are writing

You have $2$ choices for the action: move left or move right

You have $8$ choices for the new state

So: for each of the $6\cdot 4 = 24$ entries in the transition-table, you have $4\cdot2\cdot8=64$ possibilities, giving you $64^{24}$ possible Turing-machines using the quintuple formalization.

• Thanks a lot. I got everything except the last 8 choices for new state. Why 8 choices? Commented Sep 4, 2017 at 21:02
• @myadsmail There are $8$ states that any transition can go to: $Q_{Start}, Q_2, Q_3, Q_4, Q_5, Q_6, Q_{Accept}, Q_{Reject}$ ... unless a machine can never go back to $Q_{Start}$ ... but I have never seen something like that. But you may want to ask about that: can the machine ever transition back to $Q_{Start}$? If not, then there are only $7$ states that the transition can go to, and since the input only consists of $0$ and $1$ there would be no transitions going out of $Q_{Start}$ for the $*$ and U ... again, I have never seen anything like that, but you never know ... Commented Sep 4, 2017 at 21:30