← Reductions

ATM ≤m HALTTM

A computable mapping reduction proving HALTTM is undecidable, assuming ATMis undecidable. The construction wraps M into a new machine M′ that turns "accept" into "halt" and "reject" into "loop forever".

The two problems

ATM
Instance: A Turing machine M and a string w.
Question: Does M accept w?
HALTTM
Instance: A Turing machine M′ and a string w.
Question: Does M′ halt on w (in any state — accept or reject)?

The construction

Given an ATM instance ⟨M, w⟩, build a HALTTM instance ⟨M′, w⟩ where M′ is the following TM:

M' on input x:
  1. Simulate M on x.
  2. If M accepts x, halt.
  3. If M rejects x, enter an infinite loop.

The description of M′ is computable from the description of M, so the map ⟨M, w⟩ ↦ ⟨M′, w⟩ is a computable function. (No polynomial bound is required — we only need the function to be computable.)

Visualization

Step 1 / 4ATM instance
ATM instance
⟨M, w⟩
→
HALTTM instance
⟨M′, w⟩
Construction of M′
M' on input x:
  1. Simulate M on x.
  2. If M accepts x, halt.
  3. If M rejects x, enter an infinite loop.
M on wM′ on w⟨M, w⟩ ∈ ATM⟨M′, w⟩ ∈ HALTTM
acceptshaltsYESYES
rejectsloopsNONO
loopsloopsNONO
⟨M, w⟩ ∈ ATM  ⟺  ⟨M′, w⟩ ∈ HALTTM

Input ⟨M, w⟩: a Turing machine M and a string w. The ATM question asks whether M accepts w.

Correctness

(⇒) If M accepts w, then by the construction M′ halts on w. So ⟨M′, w⟩ ∈ HALTTM.
(⇐) If M does not accept w, then M either rejects w or loops on w. In both cases the construction makes M′ loop on w, so ⟨M′, w⟩ ∉ HALTTM.
Hence ⟨M, w⟩ ∈ ATM iff ⟨M′, w⟩ ∈ HALTTM. Since ATM is undecidable, HALTTM is undecidable. ∎