CSCI 510, Fall 2016, Homework # 4
1. Let A be a Turing-recognizable language consisting of Turing machines, {hM1i,hM2i,...}, where every Mi is a decider. Prove that some decidable language D is not decided by any decider Mi whose description appears in A. 2. Let A = {hRi| R is a regular expression describing a language containing at least one string w that has 111 as a substring (i.e. w = x111y for some x and y }. Show that A is decidable. 3. Let A = {hR,Si| R and S are regular expressions and L(R) ⊆ L(S)}. Show that A is decidable.
1
