4 Theory of Computation

Suppose that A is an r.e. set. Show that the sets Uxea W. and Urea Ex are both r.e. Show that Nxea W, is not necessarily r.e. as follows. For any t let K, = {x:Px(x)in t steps}. Show that for any t, K, is recursive; moreover K = Uien K, and K = Nien K x =