Question

In the fixed-point version of the recursion theorem (Theorem 6.8), let the transformation t be a function that interchanges the states $q_{accept}$and$q_{reject}$ in Turing machine descriptions. Give an example of a fixed point for t.

Short answer

Answer:

The solution is given below.

Step-by-step solution

Turing Machine.

A Turing Machine is computational model concept that runs on the unrestricted grammar of Type-zero. It accepts recursive enumerable language. It comprises of an infinite tape length where read and write operation can be perform accordingly.

Theorem is defined below.

Let us assume a fix point Turning Machine <M>

Now if our TM M halts at any input say w. In such case M cannot be a fix point because language L(M) and language t(M) will recognize must differ by w.

Now, if in case, M keeps on looping infinitely then t(M) also do the same as it its

same machine as said above with a slight difference that we have interchange the accept and reject statements depending on condition now. Thus, in this case M act as fixed point.

So we conclude that for any machine which goes in loop for infinite at any input is a fixed point.