# Impossibility Results in AI: A Survey

arXiv: https://arxiv.org/abs/2109.00484 · HTML: https://mlsanity.com/paper/2109.00484/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 128 references that are in the map.
- First posted on arXiv 1 Sep 2021.

## Builds on (most cited first, 26 of 26)

- [Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations](https://mlsanity.com/paper/1811.12359/) (2018)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Towards Robust Interpretability with Self-Explaining Neural Networks](https://mlsanity.com/paper/1806.07538/) (2018)
- [AI safety via debate](https://mlsanity.com/paper/1805.00899/) (2018)
- [Why does deep and cheap learning work so well?](https://mlsanity.com/paper/1608.08225/) (2016)
- [The Off-Switch Game](https://mlsanity.com/paper/1611.08219/) (2016)
- [Consequences of Misaligned AI](https://mlsanity.com/paper/2102.03896/) (2021)
- [Reinforcement Learning with a Corrupted Reward Channel](https://mlsanity.com/paper/1705.08417/) (2017)
- [Occam's razor is insufficient to infer the preferences of irrational agents](https://mlsanity.com/paper/1712.05812/) (2017)
- [AGI Safety Literature Review](https://mlsanity.com/paper/1805.01109/) (2018)
- [Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets](https://mlsanity.com/paper/2007.04900/) (2020)
- [Impossibility and Uncertainty Theorems in AI Value Alignment (or why your AGI should not have a utility function)](https://mlsanity.com/paper/1901.00064/) (2018)
- [Reinforcement Learning Under Moral Uncertainty](https://mlsanity.com/paper/2006.04734/) (2020)
- [Superintelligence cannot be contained: Lessons from Computability Theory](https://mlsanity.com/paper/1607.00913/) (2016)
- [The Impossibility Theorem of Machine Fairness -- A Causal Perspective](https://mlsanity.com/paper/2007.06024/) (2020)
- [The Hypervolume Indicator: Problems and Algorithms](https://mlsanity.com/paper/2005.00515/) (2020)
- [Incorrigibility in the CIRL Framework](https://mlsanity.com/paper/1709.06275/) (2017)
- [AI safety: state of the field through quantitative lens](https://mlsanity.com/paper/2002.05671/) (2020)
- [What is important about the No Free Lunch theorems?](https://mlsanity.com/paper/2007.10928/) (2020)
- [A Game-Theoretic Analysis of the Off-Switch Game](https://mlsanity.com/paper/1708.03871/) (2017)
- [Dynamic Safe Interruptibility for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1704.02882/) (2017)
- [A general theory of identification](https://mlsanity.com/paper/2002.06041/) (2020)
- [Undecidability of Underfitting in Learning Algorithms](https://mlsanity.com/paper/2102.02850/) (2021)
- [Automated Search for Impossibility Theorems in Social Choice Theory: Ranking Sets of Objects](https://mlsanity.com/paper/1401.3866/) (2014)
- [Personal Universes: A Solution to the Multi-Agent Value Alignment Problem](https://mlsanity.com/paper/1901.01851/) (2019)
- [Constraints on physical reality arising from a formalization of knowledge](https://mlsanity.com/paper/1711.03499/) (2017)

## Built on by (most cited first, 13 of 13)

- [Explainable Artificial Intelligence (XAI) 2.0: A Manifesto of Open Challenges and Interdisciplinary Research Directions](https://mlsanity.com/paper/2310.19775/) (2023)
- [LLM Censorship: A Machine Learning Challenge or a Computer Security Problem?](https://mlsanity.com/paper/2307.10719/) (2023)
- [Explainability in reinforcement learning: perspective and position](https://mlsanity.com/paper/2203.11547/) (2022)
- [The Dark Side of Trust: Authority Citation-Driven Jailbreak Attacks on Large Language Models](https://mlsanity.com/paper/2411.11407/) (2024)
- [The Alignment Trap: Complexity Barriers](https://mlsanity.com/paper/2506.10304/) (2025)
- [On the Undecidability of Artificial Intelligence Alignment: Machines that Halt](https://mlsanity.com/paper/2408.08995/) (2024)
- [The Accountability Horizon: An Impossibility Theorem for Governing Human-Agent Collectives](https://mlsanity.com/paper/2604.07778/) (2026)
- [On the Inseparability of Instructions and Data in Shared-Embedding Sequence Models](https://mlsanity.com/paper/2606.27567/) (2026)
- [Algorithmic Unverifiability of Safety for Fixed and Recursively Self-Improving Systems](https://mlsanity.com/paper/2606.28639/) (2026)
- [Prismal view of ethics](https://mlsanity.com/paper/2205.13370/) (2022)
- [Limitations on Accurate, Trusted, Human-level Reasoning](https://mlsanity.com/paper/2509.21654/) (2025)
- [The Effect of Enforcing Fairness on Reshaping Explanations in Machine Learning Models](https://mlsanity.com/paper/2512.02265/) (2025)
- [AI-Assisted Unit Test Writing and Test-Driven Code Refactoring: A Case Study](https://mlsanity.com/paper/2604.03135/) (2026)

## Abstract (arXiv)

An impossibility theorem demonstrates that a particular problem or set of problems cannot be solved as described in the claim. Such theorems put limits on what is possible to do concerning artificial intelligence, especially the super-intelligent one. As such, these results serve as guidelines, reminders, and warnings to AI safety, AI policy, and governance researchers. These might enable solutions to some long-standing questions in the form of formalizing theories in the framework of constraint satisfaction without committing to one option. We strongly believe this to be the most prudent approach to long-term AI safety initiatives. In this paper, we have categorized impossibility theorems applicable to AI into five mechanism-based categories: deduction, indistinguishability, induction, tradeoffs, and intractability. We found that certain theorems are too specific or have implicit assumptions that limit application. Also, we added new results (theorems) such as the unfairness of explainability, the first explainability-related result in the induction category. The remaining results deal with misalignment between the clones and put a limit to the self-awareness of agents. We concluded that deductive impossibilities deny 100%-guarantees for security. In the end, we give some ideas that hold potential in explainability, controllability, value alignment, ethics, and group decision-making. They can be deepened by further investigation.