ICS 1F, Homework 5

Due Friday, March 6

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.
(b) Does the existence of this translation show that M1 can simulate M2, or 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?
(d) If the reverse translation does not exist, what would that imply about the possibility that M1 or M2 might be universal?
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 }

101 11011 1

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

1 01 10 10

(c)   { 1110 ,     1 }

1 0111

(a) {	11	,	11	,	110	}
	101		11011		1

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

(c) {	1110	,	1	}
	1		0111