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 }.

Show T∈Π_{2} by
rewriting T in the form "∀∃R"
and specify that decidable R.

Describe an algorithm in BF^{H}
that semidecides the complement of T.

Prove that every problem in Σ_{3}
can be semidecided by BF^{T}.

Conclude that T is strictly 'more undecidable'
than H
by specifying a problem which is
semidecidable by BF^{T}
but not by BF^{H}.