# ITEC 420 - Section 4.2 - The Halting Problem

## Main Ideas in Section 4.2

• We define the language ATM and prove:
• ATM is recognizable but NOT decidable
• ATM' is NOT recognizable

• The proof that ATM 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 Turing-recognizable (Corollary 4.18)

• We prove that ATM' is not Turing-recognizable

• Diagonalization
• We use diagonalization to prove ATM 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

1. Assume there is a mapping from Naturals to Reals (ie that we can list all the reals)
• Use Ri to represent the real number in row i
• Use Rij to represent the digit in position j (from the decimal point) of real number Ri

2. Construct the number x as follows:
• Let the digits of x be x1, x2, x3, ...
• 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 xj = 1 + Rjj

3. Since x is a real number, it must appear on the list.
• Assume x appears at position k
• Thus x = Rk
• Thus xk = Rkk
• But, by construction, xk = 1 + Rkk
• This is a contraction

4. 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

5. This violates the assumption that our list contains all of the reals

6. 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

## ATM

• The language ATM = { <M,w> | M is a TM and M Accepts w}

## U Recognizes ATM

• U = On input <M,w> where M is a TM and w is a string:
1. Simulate M on input w
2. If M enters its Accept state, then U enters its Accept state (and accepts <M,w>)
3. 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 ATM

• Does U decide ATM?

## 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 ATM?

• U does not decide ATM
• A simulator can't decide ATM
• Could a machine decide ATM by doing additional analysis?

• Let's try to create a machine H (for Halt) that decides ATM 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: ATM is Not Decidable

2. Assume that ATM is decidable
• If ATM 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:

1. H enters its Accept state if M Accepts w (ie M enters its Accept state)

2. 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: ATM 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:
1. Construct the string <M, <M>>

2. Run H on <M, <M>>

3. D enters the state that's opposite of H
1. D enters its Accept state iff H enters its Reject state
2. 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>) =
1. D Accepts <M> iff H Rejects <M,<M>>
• (ie iff M does not Accept <M>)
2. D Rejects <M> iff H Accepts <M,<M>>
• (ie iff M Accepts <M>)

• Let's look at a picture

## The Climax

• Now, run D on its own description (ie run D on <D>)!!

• D(<D>) =
1. D Accepts <D> iff H Rejects <D,<D>>
• (ie iff D Rejects or Loops on <D>)
2. D Rejects <D> iff H Accepts <D>
• (ie iff D Accepts <D>)

• Thus, D can not exist
• Thus, H can not exist

## Thinking about the Halting Problem

• Pictures:
• ATM and TM U
• ATM 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 180-1

• Enumerate all machines: M1, M2, M3, ...

• 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 Mi on <Mi>)

• 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?

• 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 self-mentioning books
• B = a book containing a list of all non-self-mentioning 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

1. 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

2. 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:
1. Σ = {a, b}
2. Σ* = {ε, a, b, aa, ab, ba, bb, aaa, ...}
3. L = {a, ab }
4. IBS for L = 0, 1, 0, 0, 1, 0, 0 , ... (rest are 0)
5. 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!

3. 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 Turing-recognizable (Corollary 4.18)
• Can we find such a language?
• Yes. We can show that ATM' is not Turing-recognizable!

## ATM' is NOT RECOGNIZABLE

• If ATM' were recognizable, then a machine could tell if a string was NOT in ATM

• Proof:
• Assume TM V Recognizes ATM'
• If <M, w> ∈ ATM' then V halts (in the Accept state) on <M, w>
• But if X ∈ ATM' then X ∉ ATM
• Thus we can use U and V to build H (a decider for ATM, as follows:
• On input X, run U and V simultaneously.
• If X ∈ ATM then U will halt in its Accept state, and D Accepts
• If X ∉ ATM 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 Co-Turing-Recognizable

## Co-Turing-Recognizable

• A language is Co-Turing-Recognizable if it is the complement of a Turing Recognizable language

• Theorem 4.22: A language is decidable IFF it is Turing-Recognizable and Co-Turing-Recognizable

• Proof: If language A is both, we can build a machine that halts both for w in A and for w not in A.