ABSTRACT
ACCEPTTM = {M, w: M is a Turing machine that accepts w}
(where by M, w we might more properly say “encoding of M, encoding of w”). is is something that occurs several times in theoretical computer sci-
ence-the rst problem is dicult to prove, and aer that, one can use the rst problem and the idea of reducibility to prove other problems are in the same category.
