What did the proof by diagonalization actually disprove?

352 Views Asked by At

http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fourse5.html

I sort of understand the proof, but is it showing that some language are undecidable? If so, what language exactly? Because each row represent different language, ex row 1 is L1, which represent whether a string Si is accepted by M1, row 2... M2 and so on, and the diagonal is the language such that the string Si is accepted Mi.

Now, what language is shown to be undecidable?

1

There are 1 best solutions below

1
On

In your link, the diagonal describes a language. Notably, it defines the language $L$ that contains $x_{i}$ if and only if machine $M_{i}$ does not accept $x_{i}$.

This language $L$ is undecidable. To see why, note that if it were decidable, there would be some machine that decides it. This machine would be $M_{i}$ for some $i$ (since our list of machines contains all possible machines). But if $M_{i}$ accepts $x_{i}$, then $x_{i}$ isn't in our language, and vice versa, so we $M_{i}$ can't decide $L$, and we have a contradiction, and thus $L$ is undecidable.