Hacker News Reader

Comment by archgoon | Hacker News Reader

It's difficult to take this person's point seriously when he claims

>Another way to explain the shallowness of Computer Science is that it's the only discipline that eschews paradox. Even mathematics has reams of unanswered questions and potential paradox in its core philosophy. In Computer Science, there's none.

No unanswered questions? Rubbish, 'P=NP' anyone? Correctness of the assumption of the Church-Turing hypothesis (which is falsifiable if not provable) ? Granted, I'm not sure exactly what he means by "eschews paradox", but I assume this is mostly because the author doesn't really know himself. If he simply means "lacks counter-intuitive ideas", than he's dead wrong. I'll put forward the Halting Problem as an obvious example. Counter-intuitive if for no other reason than people are simply used to problems being solvable.

View on HN

If that's counterintuitive, than the most basic physics already teaches you that many things are counterintuive. The 3-body problem does not have an analytical solution. We can't even properly simulate the solar system a couple of thousands of years ahead. Nearly everything in physics is numerical approximation, despite what theory would lead you to believe. After that, the halting problem is far from surprising.

There's a significant difference between "Nobody can solve this problem, despite it having a well defined answer, regardless of the power of the computer and the time given to solve it, no matter how clever you are" and "I can only get an approximation to the solution, but the error will always be well defined, so I can get arbitrarily accurate solutions, say within a nanometer given a few billion years or so."

Although you can't solve the general halting problem, there are many halting problems that can be, and are, solved in practice. To me, that's the same thing as a numerical approximation to something that doesn't have an analytical solution.

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

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