Classes of Recursively Enumerable Sets and Their Decision Problems

Rice, H. G. (1953). Classes of Recursively Enumerable Sets and Their Decision Problems. Transactions of the American Mathematical Society, 74(2), 358-366.

Type

Journal article

Intellectual base

Primary research

Year

1953

DOI

10.1090/s0002-9947-1953-0053041-6

Link

https://doi.org/10.1090/S0002-9947-1953-0053041-6

Cited from

computer_science, mathematics

Cited by

3 citations across 3 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Axiomatic Incompatibility
  • In computability, Rice's theorem makes any non-trivial semantic property of programs undecidable.

    This sourceProves that every non-trivial semantic property of programs is undecidable.

• Computability
  • The halting problem, the Entscheidungsproblem, Hilbert's tenth problem, Rice's theorem on non-trivial semantic properties of programs, the busy-beaver function, and the Kolmogorov-complexity function are not "hard" in the resource-budget sense
• Diagonal Impossibility
  • In computability, the halting problem assumes a halting decider and builds a program that consults the decider on itself and does the opposite, and Rice's theorem extends the result to all non-trivial semantic properties via a diagonal-style flip.

    This sourceEvery non-trivial semantic property of programs is undecidable, extending the diagonal result.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:8ef8ba90677e · see in the full table