What is the definition of a computable set?
What is the definition of a partially computable set?
What is the definition of a mapping reduction from A to B.
What is the definition of an m-complete set?
Consider the set B = {p | φp(1)↓ and φp(2)↓ and φp(1) = φp(2)}. Set B contains all programs that produce the same result on input 1 as on input 2. Is B computable? Why or why not?
Show that the set A = {p | φp(1) = 1} is partially computable.
Show that the set A = {p | φp(n)↓ when n is an even number and φp(n)↑ when n is an odd number} is uncomputable. (What p does on inputs that do not look like numbers does not affect p's membership in A.)
If p is a program, L(p) is the set of all inputs that p accepts. Let Q = {p | L(p) = ∅}. Is Q computable? Prove your answer.
The halting problem HALT = {(p, x) | φp(x)↓} is uncomputable.
Is it possible to identify a pair (p, x) that is definitely in HALT?
Is it possible to identify a pair (p, x) that is definitely not in HALT?