Implication of Uncomputable Problems
post by Nathan1123 · 2025-01-30T16:48:38.222Z · LW · GW · No commentsThis is a question post.
Contents
No comments
Some problems of mathematics like the Halting Problem and the Busy Beaver Problem are uncomputable, meaning that it is mathematically proven that any Turing-complete computer is physically incapable of solving the problem no matter how sophisticated its hardware or software is. Some algorithms on a Turing machine can be used to solve special cases of these problems, but the general case is known to be uncomputable. In the case of Busy Beavers, a computer program could check each combination of programs one-by-one, but this wouldn't work for BB(6) or higher because that is believed to be larger than the number of particles in the Universe.
Wikipedia has a full list of Undecidable problems.
To what extent does this suggest that a GAI will be limited in its capabilities, even in the most optimistic scenario of AI "takeoff"? Could this present an exploitable weakness that could be used to keep an uncooperative AI contained or shut down?
Answers
No comments
Comments sorted by top scores.