Does this prove AI Safety is undecidable?


Output meaning output to computer program.

[A1] Assume we have a program that decides which outputs are “safe”.

[A2] Assume we have an example of an unsafe output: “unsafe_output”

[A3] Assume we have an example of safe output: “safe_output”.

[A4] Define a program to be safe if it always produces safe output.

[A5] Assume we have a second program (safety_program) that decides which programs are safe.

[A6] Write the following program:

def h()
   h_is_safe := safety_program(h)
   if (h_is_safe):
      print unsafe_output
      print safe_output

Clearly h halts.

If the safety_program said h was safe, then h prints out unsafe_output.

If the safety_program said h was not safe, then h prints out safe_output.

Therefore safety_program doesn’t decide h correctly.

This is a contradiction. Therefore we made a wrong assumption: Either safe output cannot be decided, or safe programs cannot be decided.

Therefore, in general, the safety of computer programs, including Artificial Intelligence, is undecidable.

Therefore AI Safety is undecidable.

  • $\begingroup$ You're passing h to safety_program, which is called from h, so safety_program will never return? If I remember correctly, the details of the Turing's proof of the Halting problem are slightly different. He uses a description of the Turing machine or maybe uses more programs or Turing machines. I would encourage you to follow exactly the idea behind Turing's proof of the Halting problem. Anyway, honestly, I would need to review his proof. It's been a long time since I read it. $\endgroup$
    – nbro
    Apr 3, 2020 at 21:24
  • $\begingroup$ nbro♦: "You're passing h to safety_program, which is called from h, so safety_program will never return?" Recursion. "If I remember correctly, the details of the Turing's proof of the Halting problem are slightly different." I adapted this proof on Wikipedia. $\endgroup$ Apr 3, 2020 at 21:32
  • $\begingroup$ Ok, I quickly reviewed Turing's proof. I don't like it (not because it is not correct, but probably because some important details are missing in this formulation of the proof or I am not fully understanding it!). The proof is based on constructing a program that does the opposite of what an oracle (that supposedly exists and works correctly) says, and this eventually leads to a contradiction. $\endgroup$
    – nbro
    Apr 3, 2020 at 21:44
  • $\begingroup$ I feel like you could prove anything with this proof. For example, suppose that "AI safety" is defined as the property of containing an "if" statement in your program. Now, safety_program should be able to return the correct answer (because this can easily be done for every finite program), but h will return the wrong answer, only because it inverts the output of the Oracle. So, you would say that safety is undecidable, while it actually is (if you use the definition above). $\endgroup$
    – nbro
    Apr 3, 2020 at 21:45
  • 1
    $\begingroup$ "safe" is just a string! "sicuro" means "safe" in Italian. What I want to say is that the word "safe" is just a word. Halting is not just a word. Halting (or not) is a behavior of the Turing machine or program. $\endgroup$
    – nbro
    Apr 3, 2020 at 22:17

3 Answers 3


You are essentially correct, although there may be some minor holes in the structure of your argument specifically. But if we're speaking informally, yes, you are correct. This is a consequence of Rice's Theorem. And it isn't just true for AI safety. All non-trivial semantic properties of algorithms (or functions) are undecidable.

"Semantic" just means it is about what the program outputs, or its behavior, both used synonymously to mean the actual result of the function, not syntax, aka the source code: the function specification itself. "Nontrivial" means that it isn't true for all programs or false for all programs.

  • 1
    $\begingroup$ Do note that Rice's theorem also shows that the question of whether a palindrome checker (for example) works correctly is undecidable in the general case, but that doesn't mean we can't be confident that any particular palindrome checker is correct. To know whether this is also the case here, you would need to properly define "AI Safety". $\endgroup$
    – Ray
    Nov 20, 2023 at 20:45

In my opinion, there are several flaws in your proof and reasonings.

First, note that, in the case of Turing's proof, h will actually loop forever (i.e. not halt) when the oracle says that h halts. In this case, there's an actual contradiction, because h will do the opposite of what the oracle says.

So, to follow Turing's proof, you would need to make h behave unsafely if the oracle says h is safe. But how should we define a safe or unsafe program? There are many unsafe behaviors. For example, in a certain context, an insult could be unsafe, in other contexts, a certain limb movement could be unsafe, and so on. So, an agent is unsafe or behaves unsafely usually with respect to another agent (or itself) or environment. You probably need to keep this in mind if you want to prove anything about the safety of AI agents.

In your second assumption, you are implicitly saying that any machine that produces the output unsafe_output is unsafe, but, of course, this definition is not a realistic definition of an unsafe program.

To help you define safety in a more reasonable and natural way, I think it may be useful to reason first in terms of artificial agents, which are higher-level concepts than Turing machines. Then you could find a way of mapping agents to TMs and attempt to prove your conjectures by using the tools of the theory of computation.

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – nbro
    Apr 4, 2020 at 2:07
  • 2
    $\begingroup$ OP already defined what it means for a program to be unsafe: that it outputs "unsafe_output." The actual contents of that are not the point. The point is HOWEVER you decide what an unsafe output is, you cannot write a program that will always be able to determine, for any and every program, whether or not that program prints unsafe output (with one caveat: this must not be a trivially true property, that is, there must exist at least one program that produces unsafe output and one that doesn't). This is a basic consequence of Rice's Theorem: en.wikipedia.org/wiki/Rice%27s_theorem $\endgroup$
    – ubadub
    Oct 29, 2022 at 16:57

The problem in your above 'proof' is that your most assumptions are actually definitions except the core A[5], and even after correcting as such, your proof doesn't really invoke Rice's theorem thus is invalid. In order to apply Rice's theorem for AI safety you must first prove AI safety is a nontrivial semantic property of programs, then you can easily prove its undecidability based on the known undecidability of Turing's famous halting problem with this same type of property. Therefore a simple syntactic property case, such as whether a program containing 'if-else' statements, can show your reasoning is invalid, since obviously the description of your program $h$ already contains 'if-else' statements syntactically! So its respective predicate if-then_program(h) always decidedly returns true and thus no contradiction at all.

AI safety is a topic of AGI including superintelligence whose software architecture and language should be as powerful as Turing complete acting as its own foundational system, and very likely be able to self-improve or self-strengthen its previous foundational system indefinitely. Thus undoubtedly AI safety in general is a nontrivial semantic property otherwise it would've been just a subset of the deductive closure of a fixed formal system as a side topic of computability theory, automated theorem provers and model checking. That's why model property checking only claims to decide whether a finite-state model of a system meets a given specification aka correctness of (finite) hardware designs or some software with clear syntactically defined liveness or safety requirements.

This is typically associated with hardware or software systems, where the specification contains liveness requirements (such as avoidance of livelock) as well as safety requirements (such as avoidance of states representing a system crash).

Model checking is most often applied to hardware designs. For software, because of undecidability (see computability theory) the approach cannot be fully algorithmic, apply to all systems, and always give an answer; in the general case, it may fail to prove or disprove a given property. In embedded-systems hardware, it is possible to validate a specification delivered, e.g., by means of UML activity diagrams or control-interpreted Petri nets.

Another way to view it as a non-trivial semantic property is to consider the possible scenario that a smarter-than-human AI well trained on pictures of faces expressing happy and sorrow emotions would later spend all its available resources to achieve a maximum happy faces goal once it has learned such value, via the means of manufacturing as many happy face pictures as possible, say. Then the AI would raise a new safety issue due to the quick unstoppable depletion of resources which would never occur in a human society since humans have nearly infinitely many different valuable evolving goals which may neither be compatible nor syntactically expressible as fixed rewards or constraints at design time. In summary the undecidability of AGI safety is like the story of Goethe's Sorcerer's Apprentice.

Having concluded AI safety's general undecidability in theory, in practice we can significant restrict the design of AGI's software architecture to be extremely conservative to ensure safety without above unintended consequences, such as inverse reinforcement learning for the AGI to learn human like reward/value function based on observed behavior from a human expert in addition to inductively learn explicitly supervised value outcomes. In the case of seeming undecidable program safety concern the agent should be able to query its human operator or a separate verifier module about any ambiguity due to insufficient or missing value training data along with self-improvement upon verification.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .