Question

i)Show that infinite decidable language has infinite decidable subset ?

ii)Show that any infinite decidable language L has an infinite decidable subset J with the property that L − J is also infinite. ​

iii. Does the statement in part i of this problem still true if L is only recognizable ? Show or Counter example.

No Spam please.

Answer 1

Let A be an infinite Turing-recognizable language. Then, there exists an enumerator E that enumerates all strings in A (in some order, possibly with repetitions). We construct another enumerator E’ that printsa subset of A in lexicographic order: “Ignore the input.

1.Simulate E. When E prints its first string w1, print w1 and let prev_w = w1.

2.Continue simulating E.

3.When E is ready to print a new string w, check to see if w is longer than prev_w (this ensures w occurs after prev_w in lex. order). If so, then print wand let prev_w = w, otherwise do not print w.

4.Go to 2.” It is clear that E’ as constructed above only prints strings in A, therefore its language is a subset of A. Since A is infinite, there will always be strings in A longer than the current prev_w – E will eventually print one of these and so will E’ (and update prev_w). Therefore, the language of E’ is also infinite. Finally, since E’ only prints strings in lexicographic order, its language is decidable as proved in (a). Thus, the language of E’ is an infinite decidable subset of A.