ICS 1F, Homework 5 Solutions

  1. Suppose we have defined two Turing machines, M1 and M2, both of which take input strings composed of the characters "0" and "1". M1 accepts strings that match the regular expression 0*1* and that have equal numbers of zeros and ones; for instance, it accepts the empty string, and the strings 01, 0011, 000111, and 00001111. M2 accepts any string which is a palindrome (reads the same forwards and backwards); for instance, it accepts the empty string, and the strings 0, 1, 00, 11, 000, 010, 101, 111, 0000, 0110, 1001, and 1111.

    (a) Show how to translate strings of zeros and ones with a finite state machine, so that M1 accepts a string s if and only if M2 accepts the translation of s.

    Answer: There are many possible translations; here's a particularly simple one. Convert "0" to "01" and "1" to "10". But if you ever see a "0" after the first "1", convert it and any following characters to a "1".

    (b) Does the existence of this translation show that M1 can simulate M2, or that M2 can simulate M1?

    Answer: that M2 can simulate M1.

    (c) Do you think you can find a similar translation in the opposite direction, so that M2 accepts a string s if and only if M1 accepts the translation of s? Why or why not?

    Answer: I don't believe a translation in the other direction exists, because the finite state machine doing the translation could not know where the middle of the string is.

    For example suppose the machine were going to translate the input "01100110". The first four characters "0110" are a palindrome, and the maching doing the translation can not know (after seeing these palindromes) that there are more characters left. So, their translation should be of the form 0i1i accepted by M1. Then the first five characters "01100" are not a palindrome, and the machine doing the translation should add more characters to the previously output string so it is no longer of the form 0i1i. But once it has done that, then no matter what else is added, it is stuck with a string that will never be accepted by M1, even though the whole string "01100110" is a palindrome.

    (d) If the reverse translation does not exist, what would that imply about the possibility that M1 or M2 might be universal?

    M1 is not a universal Turing machine, because there exist machines (namely M2) which it can't simulate.

    We would need more information to know whether M2 is universal, the translations considered so far aren't enough to tell one way or the other. (It turns out that M2 is not universal, but proving this would be beyond the scope of this course.)

  2. For each of the following sets of pairs of strings, either solve the Post correspondence problem or explain why no solution exists. (Recall that a solution is a sequence of pairs such that the concatenation of the top strings in the pairs is equal to the concatenation of the bottom strings.)

    (a)   { 11,    11,    110 }
    101110111

    Answer: 110 11 110 11 = 1 101 1 11011

    (b)   { 10,    10,    01,    0 }
    1011010

    Answer: There is no solution. If there were, the first pair in the solution would have to be (10,1) because no other pair has matching first characters. But after using that pair, the top string ends with one more character (a zero) than the bottom. Only one pair, (10,01), allows that zero to be matched, but it leaves another zero unmatched again. So, at each step you're forced to add a pair (10,01), and you can never finish this process and find a finite solution.

    (c)   { 1110,    1 }
    10111

    Answer: 1110 1110 1110 1110 1 1 1 = 1 1 1 0111 0111 0111.

    This one is pretty easy, but it shows that even when the number of pairs in an example of the Post correspondence problem is small (here there are only two pairs), the length of a solution can be quite large.