Homework 3

Solve the following problems: 5.5, 5.6, 5.7, 5.9, 5.17

In solving these problems keep the following facts in mind:

  • A is decidable iff the complement of A is decidable.
  • A is decidable iff both A and the complement of A are recognizable.
  • Atm is recognizable, but not decidable.
  • The complement of Atm is not recognizable.
  • If A <= B and B is decidable, then A is decidable.
  • If A <= B and A is undecidable, then B is undecidable.
  • If A <= B and B is recognizable, then A is recognizable.
  • If A <= B and A is not recognizable, then B is not recognizable.