Theorem: \(A_{TM}\) is not Turing-decidable.
Proof: Suppose towards a contradiction that there is a Turing machine that decides \(A_{TM}\). We call this presumed machine \(M_{ATM}\).
By assumption, for every Turing machine \(M\) and every string \(w\)
If \(w \in L(M)\), then the computation of \(M_{ATM}\) on \(\langle M,w \rangle ~~ \underline{\phantom{\hspace{2.5in}}}\)
If \(w \notin L(M)\), then the computation of \(M_{ATM}\) on \(\langle M,w \rangle ~~ \underline{\phantom{\hspace{2.5in}}}\)
Define a new Turing machine using the high-level description:
\(D =\)“ On input \(\langle M \rangle\), where \(M\) is a Turing machine:
Run \(M_{ATM}\) on \(\langle M, \langle M \rangle \rangle\).
If \(M_{ATM}\) accepts, reject; if \(M_{ATM}\) rejects, accept."
Is \(D\) a Turing machine?
Is \(D\) a decider?
What is the result of the computation of \(D\) on \(\langle D \rangle\)?
Theorem (Sipser Theorem 4.22): A language is Turing-decidable if and only if both it and its complement are Turing-recognizable.
Proof, first direction: Suppose language \(L\) is Turing-decidable. WTS that both it and its complement are Turing-recognizable.
Proof, second direction: Suppose language \(L\) is Turing-recognizable, and so is its complement. WTS that \(L\) is Turing-decidable.
Give an example of a decidable set:
Give an example of a recognizable undecidable set:
Give an example of an unrecognizable set:
True or False: The class of Turing-decidable languages is closed under complementation?
Definition: A language \(L\) over an alphabet \(\Sigma\) is called co-recognizable if its complement, defined as \(\Sigma^* \setminus L = \{ x \in \Sigma^* \mid x \notin L \}\), is Turing-recognizable.
Notation: The complement of a set \(X\) is denoted with a superscript \(c\), \(X^c\), or an overline, \(\overline{X}\).