Classes of recursively enumerable sets and their decision problems

By H. Rice. 1953

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Certified Defenses against Adversarial Examples (2018, background): “In traditional veriﬁcation work, Rice’s theorem (Rice, 1953) is a strong impossibility result essentially stating that most properties of most programs are undecidable.”
Inductive Logic Programming: Theory and Methods (1994, methodology): “Stahl's proof is based on an application of Rice's Theorem [117] on the undecidability of non-trivial index sets being recursively enumerable.”
Contrastive Code Representation Learning (2020, background): “, 2002; Bansal & Aiken, 2006), but functional equivalence is also undecidable in general (Rice, 1953).”
Utility function security in artificially intelligent agents (2014, background): “Given a possibly infinite number of quantum particles correctly pre-computing future states of the whole universe would violate many established scientific laws and intuitions (de Blanc, 2007, 2009; Rice, 1953; Turing, 1936) including the principle of computational irreducibility (Wolfram, 2002).”
Artificial Intelligence as a Positive and Negative Factor in Global Risk (2006, background): “As a result, homeotic genes are so strongly conserved that many of them are the same in humans and fruit flies—they have not changed since the last common ancestor of humans and bugs.”
LLM Censorship: A Machine Learning Challenge or a Computer Security Problem? (2023, unknown): “Theorem 1 (Rice’s Theorem [42]) .”
Abandoning Objectives: Evolution Through the Search for Novelty Alone (2011, background): “Such disagreements are natural because no measure of problem difficulty can be perfect; in general it is impossible to know the outcome of an algorithm on a particular set of data without actually running it (Rice, 1953).”
Modeling and Discovering Vulnerabilities with Code Property Graphs (2014, background): “Due to the inability of a program to identify non-trivial properties of another program, the generic problem of finding software vulnerabilities is undecidable [33].”
Goedel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements (2003, background): “Q: Aren’t there problems with undecidability? For example, do esn’t Rice’s theorem [32] or Blum’s speed-up theorem [3, 4] pose problems? A: Not at all.”