ITEC 420 - Section 4.2 - The Halting Problem

Main Ideas in Section 4.2

Diagonalization Example: Infinite Sets

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)

  2. Construct the number x as follows:

  3. Since x is a real number, it must appear on the list.

  4. In words: x is a real number and thus it must appear on the list,

  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

Review: TM Decide/Recognizes a Language


U Recognizes ATM

U - the Universal Turing Machine

A Decider for ATM?

Proof: ATM is Not Decidable

  1. Proof by contradiction

  2. Assume that ATM is decidable

A Word on Notation

Proof: ATM is NOT Decidable (continued)

The Climax

Thinking about the Halting Problem

Let's Go Over It Again

Diagonalization of M and D

Other Self-Contradictory Problems

Corollary 4.18: Unrecognizable Languages Exist

  1. The set of all Turing machines is countable. Proof:

  2. The set of all languages is NOT countable. Proof:

  3. Thus, the number of TM is countable, but the number of languages is uncountable!