Hacker News Reader

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.'

View on HN

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.

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.

Also, check out Blum's speedup theorem. Very odd.

Reply on news.ycombinator.com