The problem of determining whether a given Turing machine $ M $ accepts a given input string $ w $ is undecidable.This problem is formally known as the Acceptance Problem for Turing Machines, and is denoted by:
$$
A_{\text{TM}} = \{ \langle M, w \rangle \mid M \text{ is a Turing machine and } M \text{ accepts } w \}.
$$
What Does “Undecidable” Mean?
A language $ L $ is *decidable* if there exists a Turing machine $ D $ (called a decider) such that for every input $ x $:
- If $ x \in L $ (a member), then $ D $ halts and accepts.
- If $ x \notin L $ (a non-member), then $ D $ halts and rejects.
If no such machine exists that is, if every Turing machine that correctly accepts all members must either loop or give an incorrect answer on some non-member then the language is undecidable.
Proof by Contradiction
Assume, for contradiction, that $ A_{\text{TM}} $ is decidable. Then there exists a decider $ D $ such that:
On input $ \langle M, w \rangle $:
- $ D $ halts and accepts if $ M $ accepts $ w $.
- $ D $ halts and rejects if $ M $ does not accept $ w $ (including cases where $ M $ rejects or loops on $ w $).
Using $ D $, we construct a new Turing machine $ R $ as follows:
Machine $ R $ on input $ \langle M \rangle $ (the encoding of a Turing machine):
- Run $ D $ on input $ \langle M, \langle M \rangle \rangle $.
- If $ D $ accepts, then rreject.
- If $ D $ rejects, then accept.
Now consider what happens when $ R $ is run on its own description $ \langle R \rangle $:
- Suppose $ R $ accepts $ \langle R \rangle $. Then, by step 2, $ D $ must have rejected $ \langle R, \langle R \rangle \rangle $, which means $ R $ does not accept $ \langle R \rangle $. Contradiction.
- Suppose $ R $ rejects $ \langle R \rangle $. Then, by step 3, $ D $ must have accepted $ \langle R, \langle R \rangle \rangle $, which means $ R $ does accept $ \langle R \rangle $. Contradiction.
Thus, the assumption that $ D $ exists leads to a logical impossibility. Therefore, no decider for $ A_{\text{TM}} $ exists, and $ A_{\text{TM}} $ is undecidable.
Behavior on Members vs. Non-Members
This result hinges on the fundamental asymmetry between members and non-members:
- For members of $ A_{\text{TM}} $ (i.e., pairs $ \langle M, w \rangle $ where $ M $ eventually accepts $ w $), we can simulate $ M $ on $ w $. If the simulation halts in an accept state, we accept. Hence, $ A_{\text{TM}} $ is recursively enumerable (semi-decidable).
- For non-members especially those where $ M $ loops forever on $ w $ any simulation will also run forever and never halt. Thus, we cannot construct a machine that halts on all non-members to reject them.
Because a decider must halt on every input, and we cannot algorithmically distinguish infinite loops from long but finite computations, no decider for $ A_{\text{TM}} $ can exist.
The acceptance problem $ A_{\text{TM}} $ is undecidable: there is no algorithm that, given arbitrary $ M $ and $ w $, always correctly determines whether $ M $ accepts $ w $.
