4 ms·
The halting problem is "just a search tree with heuristics", but we don't need to go that far. We know that in general, non-exponential proofs for arbitrary tau
by pron 10y ago
The halting problem is "just a search tree with heuristics", but we don't need to go that far. We know that in general, non-exponential proofs for arbitrary tautologies exist iff coNP=NP. Now, it is true that we're not interested in the general case but in particular problems, but we already have some evidence that, at least when it comes to software verification, real-world software is bumping against the worst-case, and no amount of super-intelligence in the world is going to help reduce those exponentials. Also, there's the little problem that our statistical learning algorithms which are what passes for "AI" this time around, while able to handle lots of data, is still far from the capabilities of the average insect. Winning at Go is, theoretically, such an easy problem that I wouldn't extrapolate anything from it; the algorithm doesn't need to be really good at Go against arbitrary opponents; it just needs to beat other humans, which is a classical task for machine learning. Playing "against" math is not nearly so easy.
As it stands, both machine learning and automated theorem proving are 1) still based on algorithms developed in the '60s, and 2) their theory is not understood much better today as it was in the '60s. What changed was some brute-force search over heuristics over the years, some of which proved helpful, but mostly because our hardware is just better, but the pace isn't keeping up.
Now, it's not all doom and gloom, and there's a lot of progress that can and will be made, but it's important to understand how hard the problems are, and how primitive our current capabilities are. Of all the subdisciplines in computer science, two have experienced research winters: formal methods and so-called AI. Why? Because both seemed to show a lot of promise, a lot of progress, but ultimately ended up failing to deliver the results people had imagined they could. So both have come back with more modest goals than before, and this time their benefits seem a bit more tangible, but if people keep turning them into science fiction, we are headed into another research winter.
- kmicklas 10y ago> Winning at Go is, theoretically, such an easy problem that I wouldn't extrapolate anything from it; the algorithm doesn't need to be really good at Go against arbitrary opponents; it just needs to beat other humans, which is a classical task for machine learning. Playing "against" math is not nearly so easy. I agree. Proving "arbitrary" mathematical conjectures is surely bound to fail but all I'm saying is it might be better than humans. This would free up a lot of mental resources for the humans to do more interesting things.
- pron 10y ago> all I'm saying is it might be better than humans. Well, there's certainly no theoretical limitation of doing it as well as humans (and maybe better, as a computer is better at remembering and recalling things), and there's a lot of interesting work on automated theorem proving. But the biggest breakthrough is still based on a SAT-solving algorithm from the '60s, and we still don't understand why it works well in practice. Like in "AI", there are algorithms that work surprisingly well for some tasks, but as we don't have a theory to understand them, we don't know how to make the next breakthrough (which is essential for getting significantly ahead), so it's very hard to put a time frame on these things. Much of the perceived progress in both automated proofs and "AI" is due to new hardware allowing us to run very old algorithms on usefully-sized data, so what we're really experiencing is just finally observing the utility of very old discoveries. It's a little like finally being able to build sensors that allow us to observe physical phenomena that were theoretically assumed for a long time. But unfortunately, significant conceptual progress has hardly been made in decades (in both fields), and progress of the kind I described does not predict an imminent next step.