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 Turing-recognizable (Corollary 4.18)

We prove that A_TM' is not Turing-recognizable

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_{i_j} 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₁, x₂, x₃, ...
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_{j_j}

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_{k_k}
But, by construction, x_k = 1 + R_{k_k}
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

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

(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>) =

D Accepts <D> iff H Rejects <D,<D>>

(ie iff D Rejects or Loops on <D>)

D Rejects <D> iff H Accepts <D>

(ie iff D 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 180-1

Enumerate all machines: M₁, M₂, M₃, ...

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 Self-Contradictory 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 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

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 Turing-recognizable (Corollary 4.18)
Can we find such a language?

Yes. We can show that A_TM' is not Turing-recognizable!

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