A, B, C and D are languages. p and q are programs in a universal language, such as Turing machine programs.
What is the definition of a mapping reduction from A to B?
What is the definition of notation A ≤m B?
What is the definition of a computable set?
What is the definition of a partially computable set?
Let A = {p | p(0)↓} and let B = {p | p(1)↓}. Show that there is a mapping reduction from A to B.
Let C = {(p, q) | either p(0)↓ and q(0)↑ or p(0)↑ and q(0)↓}. Show that C is uncomputable.
L(p) is defined to be the set {x | p(x) stops and answers yes}.
Let D = {(p, q) | L(p) ≤m L(q)} Show that D is uncomputable.