[19] Let K = {x : x(x) < } be the diagonal halting set (Section 1.7). Let k1, k2,... be the list of elements of

[19] Let K = {x : φx(x) < ∞} be the diagonal halting set

(Section 1.7). Let k1, k2,... be the list of elements of K in increasing order. Define code E by E(x)=1kx 0.

(a) Show that E is a prefix-code and uniquely decodable.

(b) Show that E is not computable.

(c) Show that the decoding function E−1 is not computable.

Comments. Hint: The set K is computably enumerable but not computable. Codes with incomputable code-word alphabets are abundant, since there are uncountably many codes (prefix-codes), while there can be only countably many computable code-word alphabets.