CSci 301 Lecture Notes

Week Eight, Thursday: Mapping Reducibility

Computable Functions

For a computable function a Turing machine acts like a "black box," taking a word as input and halting with only some function of that word as output (on the tape).

Formal Definition of Mapping Reducibility

Definition 5.15. Words in set A map to words in set B and words not in A do not map to words in B.

Theorem 5.16: Decidability and mapping reducibility.

Corollary 5.17: Undecidability and mapping reducibility.

Theorem 5.22 and corollary 5.23: Turing recognizability and mapping reducibility.

Theorem 5.24: The problem of testing whether two Turing machines recognize the same language is neither Turing-recognizable nor co-Turing-recognizable.

Homework Assignment

Assigned Thursday, October 29, due Thursday, November 5:

Chapter 5, exercises 5.1, 5.3, 5.4, 5.6, and problem 5.13.

Email: Richard dot J dot Wagner at gmail dot com