6.3. Putting Mapping Reductions to Work

Let's use mapping reductions to find some more uncomputable problems.


Programs

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.


Halting and not halting

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).


An uncomputable problem

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?

Theorem. SOMETIMES-HALTS is uncomputable

Proof. Recall that

HALTTM = {(p, x) | φp(x)↓}

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

(p, x) ∈ HALT ⇔ q ∈ SOMETIMES-HALTS

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

R(p, x) = p.

Certainly, R is computable. To show that R is a mapping reduction from HALT to SOMETIMES-HALTS, we need to show that

(p, x) ∈ HALT ⇔ R(p, x) ∈ SOMETIMES-HALTS

From the definitions of HALT and SOMETIMES-HALTS, we need to show

φp(x)↓ ⇔ ∃yp(y)↓)

It is true that

φp(x)↓ ⇒ ∃yp(y)↓)

Just choose y = x. But the other direction,

φp(x)↓ ⇐ ∃yp(y)↓),

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

φp(x)↓ ⇔ ∃yq(y)↓)

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.◊


Another (similar) uncomputable problem

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 yes
Notice 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