Sketch of Solutions to Exercises

1.5.2 Each instance P of the nonemptiness problem can be transformed into an instance (P ', ) of the emptiness problem, where P’ is P with each ‘read x’ instruction being replaced by an ‘x := ?’ instruction.

1.5.3 For each instance Q(x₁, ..., x_n) of Hilbert’s tenth problem provide a program P _Q that accepts exactly those inputs that solve Q(x₁, ..., x_n) = 0.

1.5.4 For an instance of the form

Q₁²(...) + ... + Q_m²(...) .

1.5.5

(a)

For a given instance G of K₁ generate an instance (G, S S) of K₂.

(b)

For a given instance (G, x) of K₁ generate an instance (G₁, G₂) of K₂, where L(G₁) = L(G) {x} and L(G₂) = {x}.