I want to count how many Turing machines there are with $n$ states (ignoring the rejecting and accepting states) and with an alphabet (input and working) of size $c$ characters.
I have a solution, but it seems to me that it is not completely correct.
From each state we can move to $n-1$ other states ($n$ taking into account that we can stay in the original state). From each state one of $c$ symbols is possible, that is, the number of possible transitions from each state will be equal to $n*c$.
So there are $(n*c)^n$ such Turing machines, since we have $n*c$ variants of each state, and the total number of states is $n$.
If I have made a mistake in my reasoning, please explain my mistake and tell me how to correct it.
Definition of the Turing machine that is used in this problem
- A finite set $Σ$ is the input alphabet.
- Another finite set $Γ$ is the working alphabet containing all characters allowed on the tape, and $Σ ⊂ Γ$, The working alphabet contains a special character, the space: $␣ \in Γ, ␣ \notin Σ$.
- The finite set $Q$ is the set of states.
- There is an initial state $q_0 ∈ Q$.
- The transition function $δ : (Q \setminus \{q_{acc}, q_{rej}\})×Γ → Q×Γ×\{-1, +1\}$ defines the behavior of the machine at each step. If the machine is in a state $q ∈ Q$ and observes a symbol $a ∈ Γ$, then $δ(q, a)$ is a triple $(q′, a′, d)$ where $q′ ∈ Q$ is the new state, $a′$ is the symbol written on the tape in place of a, and $d ∈ \{-1, +1\}$ the direction of head movement.
- If the machine moves to an accepting state $q_{acc} ∈ Q$ or to a rejecting state $q_{rej} ∈ Q$, the machine stops.