Rice's_theorem?useskin=vector
en.wikipedia.org · 1,574 words · saved by 1 readers
Couldn't find lead section for Rice's_theorem?useskin=vector
In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, "does the program terminate for all inputs?"), unlike a syntactic property (for instance, "does the program contain an if-then-else statement?"). A non-trivial property is one that is neither true for every program, nor false for every program. The theorem generalizes the undecidability of the halting problem. It has far-reaching implications on the feasibility of static analysis of programs. It implies…
saved by
related reading
- Curry–Howard correspondenceen.wikipedia.org
- Halting problem - Wikipediaen.wikipedia.org
- Turing's proofen.wikipedia.org
- Computational Complexity Theory (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- Gödel's incompleteness theorems - Wikipediaen.wikipedia.org
- The Church-Turing Thesis (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- alan turing - computing machinery and intelligencecourses.cs.umbc.edu
- Stephen Wolfram Writingswritings.stephenwolfram.com
- Shtetl-Optimized >> Blog Archive >> Ten Signs a Claimed Mathematical Breakthrough is Wrongscottaaronson.blog
- Decision problem - Wikipediaen.wikipedia.org
- Chaitin's constant - Wikipediaen.wikipedia.org
- Algorithm - Wikipediaen.wikipedia.org