Rice's theorem

related topics
{math, number, function}

In computability theory, Rice's theorem states that, for any non-trivial property of partial functions, there is no general and effective method to decide whether an algorithm computes a partial function with that property. Here, a property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm. The theorem is named after Henry Gordon Rice, and is also known as the Rice-Myhill-Shapiro theorem after Rice, John Myhill, and Norman Shapiro.

Contents

Introduction

Another way of stating Rice's theorem that is more useful in computability theory follows.

Let S be a set of languages that is nontrivial, meaning

Then, it is undecidable to determine whether the language decided by an arbitrary Turing machine lies in S.

In practice, this means that there is no machine that can always decide whether the language of a given Turing machine has a particular nontrivial property. Special cases include the undecidability of whether a Turing machine accepts a particular string, whether a Turing machine recognizes a particular recognizable language, and whether the language recognized by a Turing machine could be recognized by a nontrivial simpler machine, such as a finite automaton.

It is important to note that Rice's theorem does not say anything about those properties of machines or programs which are not also properties of functions and languages. For example, whether a machine runs for more than 100 steps on some input is a decidable property, even when it is non-trivial. Implementing exactly the same language, two different machines might require a different number of steps to recognize the same input. Similarly, whether a machine has more than 5 states is a decidable property. Where a property is of the kind that either of the two machines may or may not have it, while still implementing exactly the same language, the property is of the machines and not of the language, and Rice's Theorem does not apply.

Full article ▸

related documents
Logical connective
Brute-force search
Isomorphism
Chinese remainder theorem
Cauchy–Schwarz inequality
Trace (linear algebra)
Locally compact space
Division (mathematics)
Field extension
Preadditive category
Unlambda
String (computer science)
Convergence of random variables
NP-complete
Axiom schema of specification
Horner scheme
Miranda (programming language)
Euler–Mascheroni constant
Transposition cipher
Splay tree
Elementary algebra
Ideal (ring theory)
Abel–Ruffini theorem
Linear map
Universal property
Gödel's completeness theorem
Natural logarithm
Projective plane
Constructivism (mathematics)
Power series