Question

Draw a TM that takes as input a sequence of 1s and doubles the input

Answer 1

SOLUTION

TM to be used : We have a Standard TM with an infinite tape and a read/write head which can move either right or left. Since the tape is of infinite length, i am gonna assume that to the left and right of our input string, we have infinite number of symbols. In this examples used to denote current status of the string, i have used symbol q to point to current position of read/write head. The current position of head would be at the character to right of q and if no character is to right of q, that means the head is currently at . So a string like 11q01 means head is currently at symbol '0'.

IDEA :  Here is how, we are gonna program the  TM. Initially all the symbols on tape of TM are 1's( For eg q111, head at leftmost 1). We will keep on moving towards right, until we reach the rightmost 1. To the right of this 1, we would have a ( this is the blank symbol, or the symbol which is present infinitely to the left and right of our input). We would change this   to 0( so current string on tape would be 111q0, head at 0)  and start moving towards left. Now we would change the rightmost 1 to X and start moving towards right (current string : 11Xq0, head at 0). We will keep moving towards right, past the zero until we encounter , We would change this to 1(current string : 11X0q1, head at 1) and start moving left. We will keep moving towards left past 0 and X's till we encounter the rightmost 1 . We would change this 1 to X( current string : 1qXX01, head at X) and start moving towards right. We would move past all X's and 0's and 1's until we encounter , we would change this to 1(current string : 1XX01q1, head at rightmost 1) and start moving towards left. This process will keep on continuing until we have exhausted all the 1's to the left of 0 by changing them to X(current String : XXX011q1, head at rightmost 1). Now when we add the last 1 to right of 0 and start moving left, we would move past 1's and 0's and X's. But since all 1's have been exhausted, we would move past the leftmost X and encounter . At this point we have added all the extra 1's we needed to add in order to double the number of 1's in the input ( you can see it from string qXXX0111 : head at leftmost X, we needed to add 3 extra ones and we have added them). Now all we need to do is change the X back to 1. So we start moving towards right and change all X's to 1's until we encounter a 0 (current String : 111q0111, head at 0). Now what we need to do is remove this 0 and shift the extra 1's we added ( 3 extra 1's in the example that we added to right of 0) towards left. To do this, we change the 0 to 1(current String : 111q1111, head at middle 1, 0 was changed to this 1) and keep moving towards right past all the 1's till we encounter . At this point we have one extra 1 than required( remember we changed 0 to 1 as well, which added an extra 1). So to do this, we move left once and change the 1 to . At this point we have our required output so we move to a final state and halt the TM.

TRANSITION DIAGRAM

In the above diagram (X,Y,R) : TM reads alphabet X, replaces it with Y and moves right.

Explanation :  We begin with state q0 and keep moving towards right past all the 1's. After reading rightmost 1 and seeing an , we replace with 0 (move left) and move to state q1 . Here we replace the rightmost 1 with X and move right. On encountering 0, we move past 0 to state q2. At state q2, we replace with 1 and move to state q3, if there is no 1 to right of 0. But if we have already added 1 ( through previous iterations) we move past those added 1's as well . After adding 1, we start moving towards left, skip through all the 1's till we reach the 0. At this point we move to state q4. We keep moving left, past all the X's. At this point we would either reach a 1, in this case we move back to state q1 and all this keeps on repeating till we have exhausted all the 1's. Once we have exhausted all 1's , we reach and move from state q4 to q5. At this point we have added all the extra 1's required. No we keep replacing X's by 1's and keep moving right. Once we reach 0, we replace it by 1 and move to state q6. We keep moving past all the 1's, till we reach ( let it stay the same and move left) and move to state q7. At q7 we replace the extra 1 with and move to final state and TM halts.