# How to write down a program of a Turing Machine with just two states that, when given the empty tape as inputs, halts after 6 steps

I’m definitely not a computer science expert, but I find this topic extremely interesting - due to this interest, I’ve recently enrolled in a class about Turing Machine.

The lecturer assigned to us an exercise and one of the questions is: ‘Write down a program of a Turing Machine with just two states that, when given the empty tape as inputs, halts after 6 steps (please note: the last step will be the one at which the machine halts. Use the simulator at http://morphett.info/turing/turing.html to count the steps. If the machine halts after 5 steps it’s enough: don’t agonise over this exercise)’. Despite professor’s suggestion, I’m agonising, and the fact that the answer (that will be evaluated) is due by tomorrow does not help. I didn’t find anything online, and the blank tape halting problem confused me more. I’m gently asking you the same question, hoping someone will help me. The best I got are programmes that loop or halt after only 2 steps. I’m using this notation: for ‘current state’ and ‘new state’ I use 0,1,2,…; for the ‘current symbol’ and ‘new state’ I use 0,1,_(blank); for the ‘direction’ I use r(right),l(left),*(do not move).

I thank in advance who will respond for the patience. I hope my question doesn’t seem too naïve or stupid.

• That machine would be Busy Beaver machine, $BB_2$. Commented Jan 12 at 15:32
• (@rus9384: isn't the tape alphabet too large?) Commented Jan 12 at 16:03
• @greybeard $BB_2=6$ is on a TM with a binary alphabet, i.e. basically "empty" and "filled" cells. Commented Jan 12 at 16:04
• (I read for...symbol...I use 0,1,_ - ternary?) Commented Jan 12 at 16:09
• Oh, yeah, in a ternary alphabet creating a TM that halts after 6 steps should be even easier. Commented Jan 12 at 16:15

It is impossible, unless your professor defined the semantics of a Turing machine in a non-standard way, or perhaps you meant at most two non-final states? Here is why:

Every Turing machine $$M$$ has at least two states: an accepting state $$q_{acc}$$, and a rejecting state $$q_{rej}$$. Whenever $$M$$ reaches $$q_{acc}$$ or $$q_{rej}$$, it halts immediately and accepts or rejects, respectively. The latter implies that every Turing machine $$M$$ with only two states must have $$q_0 \in \{ q_{acc}, q_{rej}\}$$, where $$q_0$$ is the initial state of the machine, and thus such machines either accept all inputs or reject all inputs, and they always halt after 0 steps.

If you meant at most 2 states that are not final, that is, do not equal $$q_{acc}$$ or $$q_{rej}$$, then you can do the following. Define a non-final state $$q_0$$, and let the input alphabet of the machine include the numbers in $$\{1, 2, 3, 4, 5 \}$$. Then, the machine operates as follows: $$q_0$$ is the initial state of the machine, and $$\delta(q_0, b) = (q_0, 1, L)$$, where $$b$$ stands for an empty cell (blank symbol). Then, define $$\delta(q_0, i) = (q_0, i+1, L)$$, for all $$1 \leq i < 5$$, then define $$\delta(q_0, 5) = (q_{acc}, 5, L)$$.

I assumed that the machine's tape is left bounded, and if this is not the case, it is easy to modify the solution by alternating between two non-final states $$q_0$$ and $$q_1$$ while moving between two adjacent tape-cells, upon reading increasing numbers, and I leave the details to you.

Edit: if the machine has a stop action in its transition function (indicating that the head of the machine stays in the same cell-tape and does not move left or right), then you can take the above solution and replace going left with the "stop action".