← Reductions

HALTTM ≤m ATM

The reverse direction: any HALTTM instance can be mapped to an ATM instance with the same yes/no answer. Combined with ATM ≤m HALTTM, this shows the two problems are equivalent under mapping reductions.

The two problems

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

The construction

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

M' on input x:
  1. Simulate M on x.
  2. If the simulation ever halts (accept or reject), accept.

The description of M′ is computable from the description of M, so the map ⟨M, w⟩ ↦ ⟨M′, w⟩ is a computable function.

Visualization

Step 1 / 4HALTTM instance
HALTTM instance
⟨M, w⟩
→
ATM instance
⟨M′, w⟩
Construction of M′
M' on input x:
  1. Simulate M on x.
  2. If the simulation ever halts (accept or reject), accept.
M on wM′ on w⟨M, w⟩ ∈ HALTTM⟨M′, w⟩ ∈ ATM
acceptsacceptsYESYES
rejectsacceptsYESYES
loopsloopsNONO
⟨M, w⟩ ∈ HALTTM  ⟺  ⟨M′, w⟩ ∈ ATM

Input ⟨M, w⟩: a Turing machine M and a string w. The HALTTM question asks whether M halts on w (in any state — accept or reject).

Correctness

(⇒) If M halts on w, then the simulation in M′ halts as well, so M′ reaches step 2 and accepts. Hence ⟨M′, w⟩ ∈ ATM.
(⇐) If M does not halt on w, then M′ also runs forever simulating M and never reaches step 2. So M′ does not accept w, i.e., ⟨M′, w⟩ ∉ ATM.
Hence ⟨M, w⟩ ∈ HALTTM iff ⟨M′, w⟩ ∈ ATM. Together with the forward reduction this gives ATM ≡m HALTTM. ∎