ITEC 420  Section 4.2  The Halting Problem
Main Ideas in Section 4.2
 We define the language A_{TM} and prove:
 A_{TM} is recognizable but NOT decidable
 A_{TM}' is NOT recognizable
 The proof that A_{TM} is recognizable uses machine U, the Universal Turing Machine
 Simulates the action of any Turing Machine on any input
 We prove there are languages that are not Turingrecognizable (Corollary 4.18)
 We prove that A_{TM}' is not Turingrecognizable
 Diagonalization
 We use diagonalization to prove A_{TM} is not decidable
 We illustrate diagonalization by proving that there are more
real numbers than rational numbers
Diagonalization Example: Infinite Sets
 Goal: Prove that there are more real numbers than natural numbers
 Remember: We can find a mapping from Naturals to Rationals
 Row is numerator, column is denominator
 We say that a set is countable if we can find a mapping to it from the naturals
 The Rationals are countable
 We will show that the reals are NOT countable
 Proof idea: Assume there is a mapping from Naturals to Reals and find a contradiction
Proof by diagonalization there are more reals than natural
 Assume there is a mapping from Naturals to Reals (ie that we can list all the reals)
 Use R_{i} to represent the real number in row i
 Use R_{ij} to represent the
digit in position j (from the decimal point) of real number R_{i}
 Construct the number x as follows:
 Let the digits of x be x_{1}, x_{2},
x_{3}, ...
 To the right of the decimal, digit j of x is one greater than the value
of the jth digit to the right of the decimal of the number on row j
 In other words x_{j} = 1 + R_{jj}
 Since x is a real number, it must appear on the list.
 Assume x appears at position k
 Thus x = R_{k}
 Thus x_{k} = R_{kk}
 But, by construction, x_{k} = 1 + R_{kk}
 This is a contraction
 In words: x is a real number and thus it must appear on the list,
 but by construction x cannot appear on the list
since it's different from every number on the list
 the digit at position j of x is one greater than the digit at position j of
the word in row j
 But if the word x appears at row k, then
the value of the digit at position k of x is one greater than the value of
position k of x, a contradiction
 This violates the assumption that our list contains all of the reals
 Thus there is no mapping from naturals to reals, and the reals are not countable
Review: Turing Machine Accepts/Rejects a String
 Remember: Machine M Accepts string w if w takes
M to the Accept State of M
 Machine M Rejects string w if w takes
M to the Reject State of M
 Machine M Loops on string w if w causes M to Loop indefinitely
Review: TM Decide/Recognizes a Language
 TM M decides language L iff
 if w ∈ L then M Accepts w
 if w ∉ L then M Rejects w
 TM M Accepts/Recognizes language L iff

if w ∈ L then M Accepts w
 if w ∉ L then
 M Rejects w
 or M Loops on w
A_{TM}
 The language A_{TM} = { <M,w>  M is a TM and M
Accepts w}
U Recognizes A_{TM}
 U = On input <M,w> where M is a TM and w is a string:
 Simulate M on input w
 If M enters its Accept state, then U enters its Accept state
(and accepts <M,w>)
 If M enters its Reject state, then U enters its Reject state
(and rejects <M,w>)
 If M does not halt, then U will not halt
 Clearly U Recognizes A_{TM}
 Does U decide A_{TM}?
U  the Universal Turing Machine
 We call U the Universal Turing Machine
 U is a simple model that can compute ANYTHING
that can be computed!!
 Remember special purpose vs general purpose computer
 Special purpose: computation defined by hardware
 General purpose: computation defined by software
 A UTM is like a stored program computer
A Decider for A_{TM}?
 U does not decide A_{TM}
 A simulator can't decide A_{TM}
 Could a machine decide A_{TM} by doing additional analysis?
 Let's try to create a machine H (for Halt) that decides A_{TM} by
analyzing M's behavior on w (not by simulating)
 If M halts on w (ie enters its Accept or Reject state), then
H also halts (and also enters its Accept or Reject state, respectively)
 If M loops on w, then H discovers this (by analysis, not
simulation) and enters its Reject state
 H cannot exist  let's prove it
Proof: A_{TM} is Not Decidable
 Proof by contradiction
 Assume that A_{TM} is decidable
 If A_{TM} is decidable, the some TM decides it. Call that TM H
 H must operate as follows: H(<M,w>) = On input <M,w> where M is a TM and
w is a string:
 H enters its Accept state if M Accepts w (ie M enters its Accept state)
 H enters its Reject state if M does not accept w
 H enters its Reject state if M enters its Reject state or loops
on w
 What strings does H accept? Reject?
A Word on Notation
 What do these notations represent?
 <M>
 The encoding of machine M
 <M, w>
 A pair containing an encoding of M and the string w
 <M, <M>>
 A pair containing an encoding of M and a string <M> (that is the
encoding of M)
Proof: A_{TM} is NOT Decidable (continued)
 Now use H (which we assumed to exist) to create D
 D uses H to determine what a machine does on (an encoding of) itself,
and then reverses that result!
 D = on input <M>, where M is a TM:
 Construct the string <M, <M>>
 Run H on <M, <M>>
 D enters the state that's opposite of H
 D enters its Accept state iff H enters its Reject state
 D enters its Reject state iff H enters its Accept state
 Notice the input of D: it takes an encoding of machine M and determines
whether M halts when run on (an encoding of) itself!
 Summary: D(<M>) =
 D Accepts <M> iff H Rejects <M,<M>>
 (ie iff M does not Accept <M>)
 D Rejects <M> iff H Accepts <M,<M>>
 Let's look at a picture
The Climax
 Now, run D on its own description (ie run D on <D>)!!
 D(<D>) =
 D Accepts <D> iff H Rejects <D,<D>>
 (ie iff D Rejects or Loops on <D>)
 D Rejects <D> iff H Accepts <D>
 This is a contradiction!
 Thus, D can not exist
 Thus, H can not exist
Thinking about the Halting Problem
 Pictures:
 A_{DFA} and TM M
 A_{TM} and TM U
 A_{TM} and TM H
 TM D's input and output
 TM D's internals
 TM D's internals when we run D on <D>
 TM D's inputs and outputs when we run D on <D>
 Bottom Line:
 If we run D on <D, <D>>, then we get Accept iff D Rejects <D>
 If we run D on <D, <D>>, then we get Reject iff D Accepts <D>
 How do we characterize D:
 For every encoded TM <M>, D Accepts <M> iff M does NOT
Accept <M>
 Thus, if <M> is <D>, then D Accepts <D> iff D does
NOT Accept <D>
Let's Go Over It Again
 Consider black box machine D with <D> as input
 Assume the output is Accept
 Now look inside D
 Output Accept means that the output of H was Reject
 H outputs Reject means that H Rejects <D, <D>>
 H Rejects <D, <D>> means that D Rejects or loops on <D>
 So D Accepts <D> if D Rejects or loops on <D>
 But a machine with this behavior can't exist.
 Thus H does not exist.
Diagonalization of M and D
 See figures 4.19, 4.20, 4.21, pages 1801
 Enumerate all machines: M_{1}, M_{2}, M_{3}, ...
 Build a table of running every machine on the encoding of every machine
 4.19: Use U(<M, w>) to simulate running M on w (leave blank if M Rejects or Loops)
 We can use diagonals (like proof of countable rationals), but looping
machines still causes problems
 4.20: Solution: Use H(<M, w>) to see if M
Accepts or Rejects/Loops on w
 Now consider the diagonals (ie the results of running M_{i} on
<M_{i}>)
 4.21: D must be some Mi. What values are in the line for D?
 D's entry in each column is the opposite of the diagonal for that column
 What is D's entry for D's column?
Other SelfContradictory Problems
 Barber Paradox: The barber shaves exactly those men who do not shave themselves
 Who shaves the barber?
 More precise statement: For every man x, B shaves x iff x does not shave x
 What if x is B?
 B shaves B iff B does not shave B
 Diagonalize: rows and columns: man 1, 2, 3
 Entry (i,j): man i shaves man j
 Barber's row:
 Opposite of diagonals
 Barber's column??
 More problems:
 This statement is true.
 This statement is false.
 A = a book containing a list of all selfmentioning books
 B = a book containing a list of all nonselfmentioning books
 Is A in A's list? Is B in B's list?
 M is the list of all songs not in playlist L
 N is the list of all songs not in playlist N
 Russel's paradox: Let R be the set of sets that do not contain
themselves as members.
 R = {A  A ∉ A}.
 Example 1: the set of all sets with more than one member
is a member of itself (thus it is in R)
 Example 2: The set of all sets with exactly one member is not a member of
itself (thus is it not in R)?
 Now, is R a member of itself?
Corollary 4.18: Unrecognizable Languages Exist
 The set of all Turing machines is countable. Proof:
 Every TM M can be encoded as a string <M>
 The set of strings Σ* is countable
 List all strings of length 1, length 2, ...
 To count the TM, list all strings and cross off the ones that aren't
valid TMs
 The set of all languages is NOT countable. Proof:
 An infinite binary sequence is a sequence of 0s and 1s that goes on forever
 Example: 0, 0, 1, 1, 0, 0, ...
 Each infinite binary sequence corresponds to a language over Σ
 The 1 terms of an IBS correspond to the elements of Σ* that are in the language
 Example:
 Σ = {a, b}
 Σ* = {ε, a, b, aa, ab, ba, bb, aaa, ...}
 L = {a, ab }
 IBS for L = 0, 1, 0, 0, 1, 0, 0 , ... (rest are 0)
 The second and fifth elements of Σ* are in L
 The set of all infinite binary sequences is not countable
 We can use diagonalization to show they are not countable
 Given a list of all binary sequences, we can construct one that is
not on the list!
 Thus, the number of TM is countable, but the number of languages is uncountable!
 Thus, there are more languages than Turing Machines!
 Languages exist that are NOT Turingrecognizable (Corollary 4.18)
 Can we find such a language?
 Yes. We can show that A_{TM}' is not Turingrecognizable!
A_{TM}' is NOT RECOGNIZABLE
 If A_{TM}' were recognizable, then a machine could tell if a string was NOT in
A_{TM}
 Proof:
 Assume TM V Recognizes A_{TM}'
 If <M, w> ∈ A_{TM}' then V halts (in the Accept state) on <M, w>
 But if X ∈ A_{TM}' then X ∉ A_{TM}
 Thus we can use U and V to build H (a decider for A_{TM}, as follows:
 On input X, run U and V simultaneously.
 If X ∈ A_{TM} then U will halt in its Accept state, and D Accepts
 If X ∉ A_{TM} then V will halt in its Accept state, and D
Rejects
 But of course D does not exist, so V does not exist.
 This machine would solve H, so it can't exist!
 The proof introduces the concept of CoTuringRecognizable
CoTuringRecognizable
 A language is CoTuringRecognizable if it is the complement of a Turing Recognizable language
 Theorem 4.22: A language is decidable IFF it is TuringRecognizable and CoTuringRecognizable
 Proof: If language A is both, we can build a machine that halts both
for w in A and for w not in A.