Homework 3

Distributed on Wednesday, September 17.
Please bring your solutions to the lecture on Monday, September 22.

Exercise #4:

Remember the definition of Totality:
T = { ⟨P⟩ | program P terminates on all inputs }.
  1. Show T∈Π2 by rewriting T in the form "∀∃R" and specify that decidable R.
  2. Describe an algorithm in BFH that semi-decides the complement of T.
  3. Prove that every problem in Σ3 can be semi-decided by BFT.
  4. Conclude that T is strictly 'more undecidable' than H
    by specifying a problem which is semi-decidable by BFT but not by BFH.