Question

Quick Quiz Is the following true? 1. If L is Turing-decidable, L is Turing- recognizable If L is Turing-recognizable, L is Turing- decidable 2. 3. If L is Turing-decidable, so is t 4. If L is Turing-recognizable, so is L 5. If both L and L are Turing-recognizable, L is Turing-decidable

Answer 1

1. True

A language is Turing-decidable (or decidable) if some Turing machine decides it.

A language is Turing-recognizable if some Turing machine recognizes it.

If L is Turing-decidable then L is Turing recognizable.

2. False

The converse of above does not hold---there are languages that are Turing-recognizable but not Turing-decidable.

3. True

If L is Turing-decidable then $\bar{L}$ is Turing decidable.

Proof: Suppose that M decides L. Design a new machine M′ that behaves just like M, but  If M accepts, M′ rejects and If M rejects, M′ accepts. Formally, can do this by   interchanging $q_{acc}$ and $q_{rej}$ .

Then M′ decides $\bar{L}$ .

4. False

If L is turing recognizable then it is not necessary that $\bar{L}$ is also turing recognizable. Infact if both of these are recognizable then L is turing decidable,

5. True

L is Turing decidable if and only if L and $\bar{L}$ are both Turing-recognizable.

Proof (=>):

Suppose that L is Turing-decidable.Then L is Turing-recognizable. And, $\bar{L}$ is Turing-decidable. So $\bar{L}$ is Turing-recognizable.

Proof: (<=):

Given M1 recognizing L, and M2 recognizing $\bar{L}$ . We produce a Turing Machine M that decides whether or not its input w is in L or $\bar{L}$ .