Say I define a turing machine with the following states $$Q \in \{q_0, q_1, \dots, q_n, q_{\text{halt}}\}$$ Here, $n$ is guaranteed to be finite.

Then, also have a set of rules where I do something like $$\langle q_n, \text{input}\rangle\mapsto\langle q_{n-1}, \text{output}, \text{movement}\rangle\quad n\neq 0$$ $$\langle q_0, \text{input}\rangle\mapsto\langle q_\text{halt}, \text{output}, \text{movement}\rangle\quad$$

I am wondering if this way of defining a turing machine is "proper", or if using an ambiguous amount of states $n$ and using stuff like $n\neq 0$ when defining rules of how the turing machine evolves is not allowed.


  • $\begingroup$ I'm a bit lost. I don't understand what you mean by "proper" or what concerns you have about that. I wonder if it might help to add the broader context. Why do you think $n$ is ambiguous? Of course your Turing machine will depend on $n$, but I don't see anything that makes $n$ ambiguous. $\endgroup$
    – D.W.
    Commented Apr 22 at 6:55
  • $\begingroup$ @D.W. In all the examples I've seen, all the states of a turing machine are explicitely defined, so something like this $Q \in \{q_0, q_1, q_3, q_{\text{halt}}\}$, instead of having an variable $n$ number of states. I'm just wondering if what I did is a "proper" (sorry, idk a better word lol) way, since I've never seen turing machines defined like the way i did here $\endgroup$
    – Max0815
    Commented Apr 22 at 7:01

1 Answer 1


It is fine, but by limiting your transitions to take the machine from $q_n$ to $q_{n-1}$ for every $n$, you severely restrict the power of your machines: they will take exactly $n+1$ steps and then halt, when starting from state $q_n$. You can only decide finite languages that way.

If you allow transitions from $q_m$ to $q_n$ for arbitrary $m,n$, you have unrestricted Turing machines.

You may also wish to consider intermediate cases, e.g. restricting transitions to be between states $q_m$ and $q_n$ where $m \geq n$. This will limit the Turing machines you can define, but not their power: you can still accept and decide all the same languages arbitrary Turing machines can accept and decide.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.