A universally provably safe artificial general intelligence is not possible, and the reasoning begins with the halting problem. In 1936, Alan Turing proved that no algorithm can determine, for every possible program and input, whether that program will eventually stop running or run forever. The importance of the halting problem is that it shows there are limits on what can be predicted about the future behavior of general computational systems.
The next key result is Rice’s theorem, which states that any non trivial question about what a program will eventually do is undecidable if the program is powerful enough to represent arbitrary computation. This includes questions such as whether a program will ever produce a certain output, ever enter a certain state, or always avoid a specific class of behaviors.
A highly capable artificial intelligence system, particularly if it’s a system with general reasoning ability, falls into this category. Such a system is computationally expressive enough to learn new strategies, modify its own internal structure, and operate in environments that cannot be fully anticipated. Asking whether it will always behave safely is mathematically equivalent to asking whether a general program will always avoid certain behaviors. Rice’s theorem shows that there is no universal method to answer such questions correctly in all cases.
Quantum computing does not change this conclusion. Although quantum computation can accelerate certain classes of algorithms, it does not convert undecidable problems into decidable ones. The halting problem and Rice’s theorem apply to quantum computers just as they apply to classical computers.
Provable safety is possible only when artificial intelligence systems are restricted. If the system cannot self modify, if its environment is fully defined, or if its components are formally verified, then proofs can be constructed. These proofs apply only within the specific boundaries that can be modeled and checked.
The logical conclusion is clear. The halting problem shows that prediction has limits. Rice’s theorem shows that behavioral guarantees are undecidable for general systems. Quantum computing does not remove these limits. Therefore, a fully general artificial intelligence cannot be proven safe in every possible situation. Only constrained systems can receive formal safety guarantees.
I believe Rice’s theorem applies to a programmable calculator. Do you think it is impossible to prove that a programmable handheld calculator is “safe”? Do you think it is impossible to make a programmable calculator safe?
My point is, just because you can’t formally, mathematically prove something, doesn’t mean it’s not true.
You can formally mathematically prove a programmable calculator. You just can’t formally mathematically prove every possible programmable calculator. On the other hand, if you can’t mathematically prove a given programmable calculator, it might be a sign that your design is an horrible sludge. On the other other hand, deep-learnt neural networks are definitionally horrible sludge.
I think halting undecidability and Rice’s theorem are being misapplied here.
It is true that no algorithm can determine, for every possible program and input, whether that program will halt. But for specific programs and inputs, it is often possible to figure out whether they halt or not.
I agree that there is no method that allows us to check all possible AGI designs for a specific nontrivial behavioral property. But this does not forbid us to select an AGI design for which we can prove that it has a specific behavioral property!
A universally provably safe artificial general intelligence is not possible, and the reasoning begins with the halting problem. In 1936, Alan Turing proved that no algorithm can determine, for every possible program and input, whether that program will eventually stop running or run forever. The importance of the halting problem is that it shows there are limits on what can be predicted about the future behavior of general computational systems.
The next key result is Rice’s theorem, which states that any non trivial question about what a program will eventually do is undecidable if the program is powerful enough to represent arbitrary computation. This includes questions such as whether a program will ever produce a certain output, ever enter a certain state, or always avoid a specific class of behaviors.
A highly capable artificial intelligence system, particularly if it’s a system with general reasoning ability, falls into this category. Such a system is computationally expressive enough to learn new strategies, modify its own internal structure, and operate in environments that cannot be fully anticipated. Asking whether it will always behave safely is mathematically equivalent to asking whether a general program will always avoid certain behaviors. Rice’s theorem shows that there is no universal method to answer such questions correctly in all cases.
Quantum computing does not change this conclusion. Although quantum computation can accelerate certain classes of algorithms, it does not convert undecidable problems into decidable ones. The halting problem and Rice’s theorem apply to quantum computers just as they apply to classical computers.
Provable safety is possible only when artificial intelligence systems are restricted. If the system cannot self modify, if its environment is fully defined, or if its components are formally verified, then proofs can be constructed. These proofs apply only within the specific boundaries that can be modeled and checked.
The logical conclusion is clear. The halting problem shows that prediction has limits. Rice’s theorem shows that behavioral guarantees are undecidable for general systems. Quantum computing does not remove these limits. Therefore, a fully general artificial intelligence cannot be proven safe in every possible situation. Only constrained systems can receive formal safety guarantees.
I believe Rice’s theorem applies to a programmable calculator. Do you think it is impossible to prove that a programmable handheld calculator is “safe”? Do you think it is impossible to make a programmable calculator safe?
My point is, just because you can’t formally, mathematically prove something, doesn’t mean it’s not true.
You can formally mathematically prove a programmable calculator. You just can’t formally mathematically prove every possible programmable calculator. On the other hand, if you can’t mathematically prove a given programmable calculator, it might be a sign that your design is an horrible sludge. On the other other hand, deep-learnt neural networks are definitionally horrible sludge.
I think halting undecidability and Rice’s theorem are being misapplied here. It is true that no algorithm can determine, for every possible program and input, whether that program will halt. But for specific programs and inputs, it is often possible to figure out whether they halt or not.
I agree that there is no method that allows us to check all possible AGI designs for a specific nontrivial behavioral property. But this does not forbid us to select an AGI design for which we can prove that it has a specific behavioral property!