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.