CSci 301 Lecture Notes

Week Six, Thursday: The Halting Problem

The Diagonalization Method

Theorem 4.9: ATM is undecidable.

Definition 4.10: One-to-one and onto.

Definition 4.12: Countability.

Theorem 4.14: R is uncountable.

Corollary 4.15: Some languages are not Turing-recognizable.

The Halting Problem is Undecidable

Proof

A Turing-unrecognizable Language

Theorem 4.16: A language is decidable if and only if it is both Turing-recognizable and co-Turing-recognizable.

Corollary 4.17: The complement of ATM is not Turing-recognizable.

Homework Assignment

Due in two weeks (October 29, after the mid-term exam):

TBD

Email: Richard dot J dot Wagner at gmail dot com

notes06b.htm, this hand crafted HTML file created August 31, 1998.
Last updated May 14, 2011, by Rick Wagner. Copyright © 1998-2011, all rights reserved.