Undecidable & Unrecognizable Problems

Question 1

Rice’s Theorem

Answer 1

Given any nontrivial language P over Turing machine descriptions <M> that depend only on their semantics:
- P is not the empty set and P does not contain all Turing machines
- <M> not a Turing machine description: <M> is not in P
- If L(M1) = L(M2) then <M1> is in P iff <M2> is in P</M2></M1></M></M></M>

Then P must be undecidable

Question 2

Using reduction to prove undecidability

Answer 2

L1 is known to be undecidable. If a decider L2 can be used to decide L1 (L1 can be reduced to L2), then L2 must also be undecidable

Question 3

Is A_TM decidable?

Answer 3

No

Question 4

Is A_TM recognizable?

Answer 4

Yes

Question 5

Is the complement of A_TM recognizable (i.e. is A_TM co-recognizable)?

Answer 5

No

Question 6

Is HALT_TM decidable?

Answer 6

No

Question 7

Is E_TM decidable?

Answer 7

No

Question 8

Is EQ_TM decidable?

Answer 8

No

Question 9

Co-recognizable

Answer 9

L is co-recognizable if the complement of L is recognizable

Question 10

Relationship between decidability and recognizability

Answer 10

L is decidable iff L is recognizable and co-recognizable