Question

For each of the following statements, determine if the statement is always, sometimes, or never true. Justify your statement with a proof. Hint: To prove that something isn’t always true, it is sufficient to provide a counterexample.

(a) If L is an unrecognizable language, then L is (always/sometimes/never) undecidable.

(b) If L is a recognizable language then L COMPLEMENT is (always/sometimes/never) recognizable.

Answer 1

aa)

If M decides L then M recognizes L.But not necessarily vice versa.

• In fact, these two notions define different language classes: Definition: – L is Turing-recognizable if there is some TM that recognizes L. – L is Turing-decidable if there is some TM that decides L. • The classes of Turing-recognizable and Turing-decidable languages are different.

• Theorem 2: If L is Turing-decidable then L is Turingrecognizable. • Obviously. • But the other direction does not hold---there are languages that are Turing-recognizable but not Turing-decidable.

Example: Every regular language L is decidable. – Let M be a DFA with L(M) = L. – Design a Turing machine M′ that simulates M. – If, after processing the input, the simulated M is in an accepting state, M′ accepts; else M′ rejects. Examples • Example: Let X = be the set of binary representations of natural numbers for which the following procedure halts: while x ≠ 1 do if x is odd then x := 3x + 1 if x is even then x := x/2 halt – Obviously, X is Turing-recognizable: just simulate this procedure and accept if/when it halts

b)

Four possibilities: – L and L c are both Turing-recognizable. • Equivalently, L is Turing-decidable. – L is Turing-recognizable, L c is not. – L c is Turing-recognizable, L is not. – Neither L nor L c is Turing-recognizable. • All four possibilities occur, as we will see.There are uncountably many languages. – There are only countably many Turing-recognizable languages and only countably many co-Turing-recognizable languages. – Because there are only countably many Turing machines (up to renaming)