Exam 2 question 7

Set A is not computable.

Proof. A is nontrivial because some programs satisfy the required property for membership in A, and some do not.

A respects equivalence. Suppose that p and q are two equivalent programs.

p ∈ A	⇒	φ_p(n)↓ when n is an even number and φ_p(n)↑ when n is an odd number
	⇒	φ_q(n)↓ when n is an even number and φ_p(n)↑ when n is an odd number	(since p ≈ q)
	⇒	q ∈ A

By Rice's theorem, B is uncomputable.