T11-PP1: (Turing Machine programs) -- SOLUTION SKETCH
(a) Practice Prob 2 on Section 11.3 of [SG].
(S1,1,0,S2,R) // at odd positions, change 1 to 0, move R
(S2,1,1,S1,R) // at even positions, leave 1 unchanged, move R
State Tape Rule to use
----- ------------------ ----------- // initial state
[S1] ... b[1]1 1 b ... (S1,1,0,S2,R) // odd position, change to 0
[S2] ... b 0[1]1 b ... (S2,1,1,S1,R) // even position, leave unchanged
[S1] ... b 0 1[1]b ... (S1,1,0,S2,R) // odd position, change to 0
[S2] ... b 0 1 1[b]... Halt. // even position, leave unchanged
(b) Practice Prob 3 of Section 11.5 of [SG] -- SOLUTION SKETCH
(S1,1,1,S1,R) //move right, leave string unchanged (S1,0,0,S1,R) //move right, leave string unchanged (S1,b,1,S2,R) //reached end-of-string; write a 1 & haltNote: The first two instructions together can be considered a primitive operation to move to the right (skipping over strings of 0s and 1s). Thus, you can use this method to "move" the TM to the right or to the left (change the "R" to "L") -- by assigning a new state, if necessary.
(c) Problem 13 of Chapter 11 of [SG].
[Similar to previous problem above. So, DIY.]
(c) Problem 8,13 on p.551-2 of Chapter 11 of [SG].
T11-PP2: (Executing a Turing Machine Program) --- DIY
(S1,1,1,S1,R) // always write 1, move right (S1,0,1,S1,R) // always write 1, move right
T11-D2: (TM) -- SOLUTION SKETCH -- Problem 17 of Chapter 11 of [SG].
(S1,1,1,S2,R) // odd positions: leave 1 alone, move right, goto S2 (S2,1,0,S1,R) //even positions: change 1 to 0, move right, goto S1
Try the TM on several inputs to see what it does.
The first two instructions are similar to those of T11-PP1(b) --
they move the TM to the right, leaving the original string unchanged.
It then moves forever to the right, changing blanks ("b") to 1's.
**INFINITE LOOP**
(S1,1,1,S2,R) //first (mod 3) 1-symbol, leave it alone (S2,1,1,S3,R) // 2nd (mod 3) 1-symbol, leave it alone (S3,1,0,S1,R) // 3rd (mod 3) 1-symbol, change to 0, restart at S1
First, algorithm to increment a binary string is to scan from right to left and change 1's to 0, until (a) we see the first 0 which we change to a 1, or (b) we see a blank, which we also change to a 1. Then we stop. So, first, we move right to the right-most digit. (State S1) Do the increments part: change 1's to 0's, move left; (State S2) Terminate on seeing a 0 or a blank, go to State S3 [terminating] (S1,1,1,S1,R) //move right (S1,0,0,S1,R) //move right (S1,b,b,S2,L) //found right-most digit; change to S2; (S2,1,0,S2,L) //repeatedly, change 1s to 0s. move left; (S2,0,1,S3,L) //found a 0, change to 1, terminate; (S2,b,1,S3,L) //found a b, change to 1, terminate; Not so hard, right? If not, try it on ...b010b... or b0101111b...
First, the idea behind this: This is similar to bit-flip and parity. So, a very simple, but inefficient method will be to do one, then go back, and do the other. (You can do a TM-prgram for that.) But, a better way is to do both simultaneously. Bit flip is simple (just make sure you write the opposite symbol every time). The key is to "remember" the parity of the *output* string. Have one state (S1) for even parity (# of 1s in the output), and another state (S2) for odd parity. At the end of input, append the appropriate parity bit and END. (S1,1,0,S1,R) //flip bit, output is 0, still even parity; (S1,0,1,S2,R) //flip bit, output is 1, change to odd parity; (S2,1,0,S2,R) //flip bit, output is 0, still even parity; (S2,0,1,S1,R) //flip bit, output is 1, change to even parity; (S1,b,1,S3,L) //reached end; add parity bit (1). END (S2,b,0,S3,L) //reached end; add parity bit (0). END I leave you to draw the state diagram. (Hard to draw with html).