Exercise 8:

K    {pMp(1)Mp(2)}\overline{K}\;\leq\;\{ p \mid M_p(1){\downarrow} \,\wedge\, M_p(2){\uparrow} \}
Reduce K\overline{K} to the set of natural numbers such that the program codified by them halt with input 11 and do not halt with input 22 (roughly, the set of programs that halt with input 11 and do not halt with input 22), in order to prove that such set is not semi-decidable (not recursively enumerable).
Authors: Carles Creus, Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.