# Reference for an undecidability proof [duplicate]

I'm searching for a reference of an undecidability proof that is as simple as possible and starts "from scratch".

With "from scratch" I mean that it does not use some other undecidable problem to prove some undecidability (which is the usual case), I cannot wrap my mind about how proving undecidability that way (without a previous proof) could be possible.

This question may be inspiring: An example of an easy to understand undecidable problem

Also, I know this is probably not very objective, but it is important to me, it should be something as simple as possible, hopefully enough so that even I can understand it.

## marked as duplicate by Raphael♦Oct 4 '13 at 6:52

• The first languages to be proven undecidable were - if I'm not mistaken - shown to be so via diagonalization. Unless you need a constructive proof, the most simple proof is that there is an uncountable number of languages but only a countable number of algorithms (since each word encodes at most one algorithm, and words are countable). If you are looking for a constructive proof, I would recommend to read Arora & Barak: Computational Complexity - A Modern Approach, p.25 under the heading "1.4 Uncomputable Functions". – G. Bach Oct 3 '13 at 15:22
• G.Bach: diagonalization is a constructive proof, it gives an explicit language which is not decidable. – sdcvvc Oct 3 '13 at 16:49
• What's wrong with a basic proof of the undecidability of the halting problem? Consult, for instance, comp.nus.edu.sg/~cs5234/FAQ/halt.html – Patrick87 Oct 3 '13 at 20:11
• Since you don't give us any indication of which proof you don't get, I think this is covered by our reference question. There is, of course, always my favorite $\pi$ question for developing intuition. – Raphael Oct 4 '13 at 6:52
• I found a very simple proof. I don't think it can get any more simple than that. – Trylks Jul 24 '14 at 10:15