State Change in a Turing Machine(Computer of Integer Function)

1.2k Views Asked by At

Im trying to learn how TM can be used as a computer of integer functions. I have this problem

enter image description here

The text books gives the construction as follows

enter image description here

I understand that intially the R/W head will be at position on the tape with $0$ and the state will be $q_0$. It goes on scanning (replacing zeroes by zeroes). On getting a $1$ it replaces it by $0$ and changes it state to $q_1$. So if I understand right if there is an unmatching symbol to be replaced there is a state change. So on reaching $q_1$ and when a Blank is read, the state is changed to $q_2$. Why is that?

1

There are 1 best solutions below

0
On

You initially start with $0^m10^n$ on the tape followed by infinite B. In state $q_0$ you read the first $0$s and leave them unchanged. When you reach the $1$ it change it to a $0$ and move to $q_1$. At this point the tape is $0^m00^n$ you thus have $m+1+n$ $0$s. Hence you have to remove a $0$ in order to have $m+n$ that is what is done in $q_1$.

In $q_1$ you read all the $0$ until the end of the string, when you reach the end (reading a B) you go back on step end remove the last $0$ and thus get $0^m00^{n-1}=0^{m+n}$.

I hope it is clearer.