Let's use mapping reductions to find some more uncomputable problems.
Up to now, I have followed Sipser's approach of distinguishing between a Turing machine M and its description as text, ‹M›. But that is not really necessary. Instead, just think of a program. Since a program is already text, we don't need to convert it to text.
If p is a program, then φp is the function that p computes.
I will write φp(x)↓ if φp(x) ≠ ⊥ (that is, if program p eventually halts on input x).
I will write φp(x)↑ if φp(x) = ⊥ (that is, if program p loops forever on input x).
Define
SOMETIMES-HALTS = {p | ∃ y φp(y)↓}That is, SOMETIMES-HALTS is the problem where the input is a program p and the question is, does there exist at least one input on which p eventually stops?
Proof. Recall that
Let's just call HALTTM by the shorter name, HALT. We know that HALT is uncomputable. To show that SOMETIMES-HALTS is uncomputable, it suffices to find a mapping reduction from HALT to SOMETIMES-HALTS.
Given pair (p, x), where p is a program and x is a string, we need to find another program q such that
We really need to do a little more than that; we need to find a computable function R so that q = R(p, x) is the desired program q.
First, let's try a reduction that does not work, just to get a better idea of what the problem is. Suppose we try
Certainly, R is computable. To show that R is a mapping reduction from HALT to SOMETIMES-HALTS, we need to show that
From the definitions of HALT and SOMETIMES-HALTS, we need to show
It is true that
Just choose y = x. But the other direction,
is not true. What if p halts on some parameter other than x?
So we cannot choose q = p. We need to build different program q.
Keep in mind that, when writing down q, we have p and x in hand. An idea is to make q ignore its input, and to run p on input x.
Define R(p, x) = qp, x where qp, x is as follows.
qp, x(y) Run p on input x, and yield the same result that it yields.
Now it should be clear that, for every p and x, if q = qp, x then
which is exactly what we need. It should also be clear that R is computable. It is easy to write a program R that, given p and x, writes down program qp, x.◊
Here is a similar proof, using a similar reduction. Define
Y1 = {p | φp(1) = yes}Thought of as a computational problem, a program G that solves Y1 must take input p and tell whether p (stops and) answers yes on input 1. Notice that G is not supposed to answer yes on input 1. The input to G is a program, and G must say where that program answers yes on input 1.
Theorem. Y1 is uncomputable.
Proof. It suffices to find a mapping reduction R from HALT to Y1. Notice that an input to HALT is an ordered pair (p, x), so the input to R is also a pair (p, x). The input to Y1 is a program, so the output of R is a program.
Define R(p, x) = qp, x defined as follows.
qp, x(y) 1. Run p on input x. 2. Answer yesNotice that, if q = qp, x, then
(p, x) ∈ HALT | ⇒ | φp(x)↓ |
⇒ | φq(y) answers yes for every y | |
⇒ | φq(1) answers yes | |
⇒ | q ∈ Y1 |
The other direction works too.
q ∈ Y1 | ⇒ | φq(1) answers yes |
⇒ | φp(x)↓ (since q only answers yes if it finishes step 1) |
|
⇒ | (p, x) ∈ HALT |