Hacker News Reader

>One of the first things you learn in Computer Science is that not all problems can be solved with a computer.

Oh ... could you elaborate? I think my cut-rate, community college degree skipped that part :) it seems like a useful thing to know!

View on HN

I assume skywhopper is referring to undecidable and uncomputable problems. https://en.wikipedia.org/wiki/Undecidable_problem

I don't really get how that's a critique of the ability to represent complexity on a computer well. After all, isn't a human mind constrained by P ?= NP in the same way as a computer architecture?

We do not know that actually. While it might be true that classical mechanics is the only machine behind our brain, evolution is just as likely to have stumbled into a quantum computer design we have not yet discovered in the last billion years.

Quantum computers still can't solve NP-complete problems in polynomial time, sadly. Take a look at the BQP complexity class; it's only a subset of NP.

Here's a big one:

https://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_th...

Reply on news.ycombinator.com