Hacker News Reader

Comment by visarga | Hacker News Reader

> we can craft questions that cannot be answered using Boolean algebra alone

Sure, that's trivial, the travelling salesman problem for example can't be solved exactly, but approximative methods come very close. Given that brains are pattern recognition machines generating probabilities we're already in the approximative regime. Nothing is certain, even science has its revisions.

So does it matter if we can only approximate? For living things the main thing that matters is life, self reproduction, not exactness. As long as they reproduce they are still valid, with all imperfections and approximations. I think the only questions that matter are those related to life, there are plenty of uncomputable things outside self reproduction. This is for biological agents, an AI would be using evolutionary methods to reproduce their digital genes instead.

View on HN

The traveling salesman problem can absolutely be solved exactly. It just takes a lot of time.

Computability doesn't take into account how fast you can solve a problem: only if it is possible to solve it at all.

It's exponential, you can solve it for N=100, but not for N=1,000,000. You can't say "it just takes a lot of time" if that time is > age of the universe.

Actually, you can. There's a huge gulf between things that we know we could compute given enough time, even if that time is impossible to actually be given, and things we know can never be computed given infinite computing power.

Something like the perfect security of either hiding or binding in a commitment protocol can never be broken given computers of infinite capacity and speed because it's mathematically impossible. That is opposed to computational security, which only states that the property can't be broken within any usable time frame. This is often in the order of hundreds of millions of years in practical cryptographic systems. The point is, it can be technically be done.

Breaking RSA can factored just by brute forcing. It might take a lot of time, but actually doing it is not hard for sufficiently small keys. We just increase the key size until it takes a long time.

> You can't say "it just takes a lot of time" if that time is > age of the universe.

1. The difference matters a WHOLE LOT when you're studying computability. If the question you're trying to answer is "Can this be computed exactly?", then the distinction is paramount.

2. Your argument here is functionally equivalent to stating that there exists a largest number since it's trivial to construct a number which would require more digits (in any base you'd like) than subatomic particles in the entire universe to represent in its fully-expanded form… so let's pick this one as the largest and stop worrying about all of that infinity hub-bub!

There is a fundamental difference between "We don't know how to solve this practically since the best solution we have would take too much time." and "It is a problem without solution. It can not be solved at all not matter how you approach it, or even how an imaginary alien specie with technology beyond our understanding would approach it".

Also, the equivalence between the different models of computation for Turing completeness (turing machine, lambda calculus, ...) isn't about complexity classes of the problems, only wether or not the model allow to solve the same set of problems. For example searching in a sorted array is O(log n) on a Von Neumann machine but O(n) on a Turing machine.

Reply on news.ycombinator.com