Hacker News new | past | comments | ask | show | jobs | submit
Step 1: solve the halting problem.
Yep, calling it an "unsolved" problem is a misnomer. We already have mathematical proof that it's impossible.

But that aside, it's such a shame that many drinking the AI Kool-Aid aren't even aware of the theoretical limits of a computer's capabilities.

loading story #48249094
You're probably thinking of Rice's theorem (a sort of generalised halting problem), but this task is actually way easier than that, since we're not trying to study arbitrary algorithms: we're trying to study the subset of human-comprehensible algorithms. Most of the things we want computers to do are things that, given enough time, someone can write a program to solve: and generally, those programs are not tricksy or meta, and don't involve unsolved mathematics problems found by studying busy-beaver candidates. If it's possible for a human to understand how a program works (which is a necessary component of writing such a program), it's possible to write a mathematical proof about the program's behaviour, and that means it's in principle possible to automate the construction of that mathematical proof, which is equivalent to the "determine whether code conforms to the spec" task.

"Somewhat easier than an impossible task" is not a particularly strong claim about when (or whether) this problem will be solved, though.

loading story #48249746
loading story #48249029