# Is this formulation for a turing machine proper?

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.

Thanks!

• 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.
– D.W.
Commented Apr 22 at 6:55
• @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 Commented Apr 22 at 7:01

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.