7.1 Turing Machine Acceptance ProblemWilliam Umboh
The University of Melbourne
The TM Acceptance problem is as follows: given an encoding
⟨ M ⟩ \langle M \rangle ⟨ M ⟩ M M M w w w M M M w w w
Equivalently, we define the language A T M A_{TM} A TM ⟨ M , w ⟩ \langle M, w \rangle ⟨ M , w ⟩ M M M M M M w w w
The following Turing machine U U U A T M A_{TM} A TM
On input ⟨ M , w ⟩ \langle M, w \rangle ⟨ M , w ⟩ M M M w w w M M M M M M
The simulation can be done in a similar fashion as for DFAs. Details
omitted.
To prove that it recognizes A T M A_{TM} A TM U U U ⟨ M , w ⟩ \langle M, w \rangle ⟨ M , w ⟩ M M M w w w M M M w w w
M M M
M M M
M M M
By definition, if M M M U U U U U U U U U ⟨ M , w ⟩ \langle M, w \rangle ⟨ M , w ⟩ M M M w w w
It is tempting to claim that the following TM decides A T M A_{TM} A TM
On input ⟨ M , w ⟩ \langle M, w\rangle ⟨ M , w ⟩
Simulate M M M w w w
Accept if M M M
Reject if M M M
Reject if M M M
The issue is that “Reject if M runs forever” is not a valid TM action.
An actual run of the TM.
7.1.1 Universal Turing machines ¶ The fact that we can design a Turing machine that takes as input an
encoding of another Turing machine and simulate it is referred to as the
“universal” nature of Turing machines. In contrast, finite automata and
pushdown automata do not have this feature: there is no universal finite
automaton (pushdown automaton, resp.) that can take an encoding of a
finite automaton (pushdown automaton, resp.) and simulate it.
Universality also has huge practical importance. For example, your
mobile phone is not a single-purpose device: by loading different apps,
it can take on other functionality. Without universality, you need one
device to browse the Internet, a separate one to play music, and a
separate one to make
calls .
7.1.2 Decider for TM Acceptance too good to be true ¶ It turns out that TM Acceptance is undecidable. Before we show that,
let’s build some intuition first by showing that a decider for TM
acceptance is too good to be true: using such a decider, we can turn any
recognizer into a decider.
Suppose that A T M A_{TM} A TM L L L L L L L L L
Let M M M L L L U U U A T M A_{TM} A TM D D D L L L
On input w w w
Run U U U ⟨ M , w ⟩ \langle M,w \rangle ⟨ M , w ⟩
Accept if U U U
Reject if U U U
Since U U U D D D w w w D D D M M M w w w L ( D ) = L ( M ) = L L(D) = L(M) = L L ( D ) = L ( M ) = L D D D L L L