Instantaneous Description Turing Machine
In this class, We discuss Instantaneous Description Turing Machine.
For Complete YouTube Video: Click Here
The reader should have prior knowledge of the Acceptance of Turing machine. Click Here.
We do not learn any new concepts here.
We showed you the acceptance and rejection of input strings using the Turing machine in our last class.
In the exam, how do we show acceptance and rejection?
We need some representation to show the acceptance and rejection of the input string.
The instantaneous description is one such representation to show the acceptance and rejection of the input string.
The below diagram shows the Turing machine for the language strings containing palindromes.
Example: Take the input string 1001.
given below is the instantaneous description for the input string 1001.
q0 1001
We start from state q0. We take the input string in our instantaneous description.
On state q0 with input symbol one, we move to state q4.
We convert the input symbol 1 to ‘y’ and move right.
We show the above transition as Yq4 001
We convert the first one to ‘y’, and the state is mentioned after ‘y’.
In the instantaneous description, We do not mention the blank symbols.
Whenever we move beyond input symbols, we assume them as blank symbols.
The below description shows the next transition
On q4, the input symbol is 0. We move right.
We show the instantaneous description as Y0q4 01.
Similarly, the next transitions are.
Y00q4 1
Y001 q4
Now we have blank as input on state q4.
Y00q5 1
Y0q3 0Y
Yq3 00Y
q3 Y00Y
Yq0 00Y
YXq1 0Y
Similarly, you try to write the remaining descriptions.
We accept the input if the instantaneous description finally had a q10 state. Otherwise, We reject the string.