Interesting results in TCS which are easily explainable to programmers without technical background Suppose you're meeting with programmers who have taken some professional programming courses (/ self thought) but didn't study a university level math.

In order to show them the beauty of TCS, I'd like to gather some nice results/open questions coming from TCS which can easily be explained.

A good candidate for this purpose (IMHO) will be showing that the halting problem is not decidable. Another will be showing a lower bound on the running time of comparison based sorting (although that's a bit pushing it from what I expect them to understand).

I can also use the ideas from Explain P = NP problem to 10 year old, assuming some of them are unfamiliar with it.

So, questions has to be:

(0. Beautiful)


Explainable with (at most) high school math.
(preferably) not trivial enough to be shown in professional programming courses (for C++/Java/Web/etc.).
In addition to the halting problem, I suggest discussing:

Rice's Theorem.  Some of the explanation on Wikipedia is a bit jargon-heavy, but it's generally not a hard theorem or proof to understand other than that; it has a lot of relevance to real-world concepts like anti-virus software.  The proof is about as involved as the proof of the halting problem (and actually depends on the undecidability of the halting problem).  Basically, just understand that a "computable function" is a Turing machine or computer program.