Non Halting Turing Machine || Lesson 90 || Finite Automata || Learning Monkey ||

Описание: Non Halting Turing Machine
In this class, We discuss Non-Halting Turing Machine.
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*.
At least 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 turning 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.


Link for playlists:
   / @wisdomerscse  


Link for our website: https://learningmonkey.in

Follow us on Facebook @   / learningmonkey  

Follow us on Instagram @   / learningmonkey1  

Follow us on Twitter @   / _learningmonkey  

Mail us @ [email protected]