Turing Machines

a. Design a TM that accepts the language of odd integers written in binary. Solution.
b. Design a TM that accepts the language a#b#c#, where a, b, c are in {0, 1}*, and a+b = c, where a, b, and c are interpreted as positive binary integers. Solution.
c. Design a TM that enumerates the language of odd integers written in binary. Solution.
d. Think about how tedious it would be to design a TM that enumerates all primes in binary.

---

a. To accept odd-valued binary strings, we only have to look at the last bit. The TM moves right until it reads a blank, moves left one space and accepts if and only if there is a 1 on the tape.

 

 

 

 

 

 

b.Simulate adding a and b, marking the digits right to left as we go and verifying the digits of c.

1. Add a $ to the beginning of the tape and shift the rest of the input.
2. Move right past the input string, write another # and a 0. This is the carry bit. Move left until you hit the $.
3. Move right to the first #, then move left until you find an unmarked digit.
4. Remembering this digit, move right past a #.
5. Move right to the second #, move left until you find an unmarked digit.
6. Remembering this second digit, move right past the second #.
7. Move right past the last #.
8. If the two bits read, plus the carry bit, are equal to 2 or 3, write a one to the carry bit.
9. Move left past the # and stop at the first unmarked bit. If the remembered bits plus the old carry bit are equal to 1 or 3, check for a 1 under the head, and mark it. Otherwise, check for a zero, and mark it. Reject if the check fails.
10. Move left to the $, and repeat from 3.
11. When there are no unmarked digits in a and b, move to the carry bit.
12. If the carry bit is 1, check for an unmarked 1 in c. Accept as long as there are no unmarked 1s in c.

 

 

 

 

 

 

 

c. This solution is a bit non-intuitive, because it does not construct the odds by adding one each time, but by constructing all possible odd-valued n-bit strings by prepending 0 and 1 to all odd-valued n-1 bit strings. The resulting machine, though, is considerably simpler.

1. Write $*1* to the tape
2. Move to the left pass a * and until you hit another *.
3. Moving right, copy symbols to the end of the tape, replacing the first * with *0, and #s with #0. Stop when you encounter a second *. Don't copy it.
4. Move left back past two stars and stop on the third.
5. Copy the string between the stars again to the end of the tape, this time prefixing each bit with a 1. Also, this time write a # instead of a leading *. Stop when you get to the second *, but copy it to the end of the tape.
6. From the end of the tape, repeat back to step 2.