Acceptance of Turing Machine by Halt State

In this class, We discuss the Acceptance of Turing Machine by Halt State.

For Complete YouTube Video: Click Here

We use the example we discussed in constructing the turning machine class. Click Here.

The below diagram shows the Turing machine for the language accepting palindromes.

The state q10 is considered a halt state.

Whenever we need to accept the string, we move the state q10.

We did not mention any transition on halt state.

We move to the halt state and accept the string.

We take two examples and understand how strings are accepted and rejected in the Turing machine.

Example 1:

Input: B1001B

We start in state q0.

On state q0, if we see input symbol 1, we go to q4.

The state q4 is used to move right to the end of the string.

We move and convert the last one to y.

On the state q3, we move back to the second input symbol.

The second symbol is converted to and moved to the last before the symbol.

We convert the last before symbol to x.

Now all the inputs symbols are over. We are at the state q0.

On the state q0, if we see the input symbol x, we move to q10 and accept the input.

Input: B1000B

First, we covert the input symbol one and move to the q4 state.

Using the state q4, we move to the last input symbol and move to state q5.

On state q5, we did not mention the transition for input symbol ‘0’.

Here the Turing machine will stop and reject the input.

Suppose the Turing machine stopped in any non-halting state. The input is rejected.