Non Halting Turing Machine

In this class, We discuss Non-Halting Turing Machine.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of Turing machine construction. Click Here.

We take an example and understand non-halting turing machine.

Take an input alphabet Σ = { a, b}

The language L = aa*.

Atleast one a followed by any number of a’s.

The below diagram shows the Turing machine for the language L.

The above turing machine works for a few inputs.

The below diagram shows a few input strings.

Let’s understand how it works on the inputs.

The turing machine should accept the first input ‘aaa’. 

Yes, the input aaa is moving to a halt state.

The second input, baa, is rejected. Yes, the turing machine rejects.

The third input, ‘aba,’ should be rejected. But we are moving in a loop.

In the turing machine, we move to state q1 after taking the first input symbol a.

On state q1, if we find b, we move left. So we move to the first input symbol.

On state q1, if we see input symbol a, we move right. We come to input symbol b.

We move left and right without a halt.

The above turing machine we call non-halting turing machine.

For accepted inputs, the turing machine is halting.

The Turing machine may halt by rejecting the input or loops without halting for rejected inputs.

Why do we have a non-halting turing machine?

On the Turing machine, we are moving left and right, forming a loop.