0

Let $E$ be a Turing machine outputting a list of codes of Turing machines $\{\left \langle M_1 \right \rangle, \left \langle M_2 \right \rangle, ...\}$ where every $M_i$ is deciding some language $L_i$.

How do I prove that there is a decidable language that is not one of the languages $L_i$

I know I have to use the diagonal argument but how do I formulate it in the proof?

sxd
  • 3,504
Graham
  • 1

1 Answers1

3

Let $Q$ be the set of those numbers $n$ (written in unary notation, say) such that $n\notin L_n$. Clearly, $Q$ is not one of the languages $L_n$ since they disagree about $n$. Yet $Q$ is decidable, as follows. On any input that isn't a unary notation, just say no. On an input that is the unary notation for a number $n$, use $E$ to figure out what $M_n$ is, and then run $M_n$ to decide whether $n\in L_n$; output the opposite of the answer you got from $M_n$.

Andreas Blass
  • 71,833
  • So $Q$ is decidable, but obviously $Q$ isn't a language decided by any $\langle M_i\rangle$. Nice explanation of the standard diagonalization argument. +1. – Rick Decker Apr 05 '13 at 01:33