News for hackers. Stuff that matters.
Re:Go To University, Not For CS by gwern on Sunday May 30, 2010 @10:20PM (#1391613)
Just a quick nitpick - I've known people to be not particularly impressed by the Halting Problem.

The real result, if you want to wow someone, is Rice's theorem (http://en.wikipedia.org/wiki/Rice%27s_theorem): 'Not only can you not decide halting - you can't decide anything else either.'

Re:Go To University, Not For CS by archgoon on Sunday May 30, 2010 @10:50PM (#1391648)
Really? They're impressed by Rice's theorem but not the Halting Problem? I find that surprising, I would expect someone unimpressed with the Halting Problem would simply view Rice's theorem as an obvious consequence of the Halting Problem.
Re:Go To University, Not For CS by gwern on Monday May 31, 2010 @11:52AM (#1392749)
If you aren't impressed by the Halting Problem, you probably aren't so sophisticated and able that Rice's theorem is an obvious extension of the Halting Problem.

Intuitively, I can convince myself that Rice's theorem is true ('just write a program that runs itself and halts or doesn't halt on whether it has that property'), but I can't really follow the math and I only think of that because I've already heard of a number of results that use similar translations/compilations from one sort of program to another.

Re:Go To University, Not For CS by mreid on Monday May 31, 2010 @06:25AM (#1392259)
Also, check out Blum's speedup theorem. Very odd.