Classes of recursively enumerable sets and their decision problems
Open accessThe DOI matches its Crossref record; 12 of the 14 references it cites were found in a registry or an index.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Gödel, K. (1931) · Monatshefte für Mathematik und Physik · doi:10.1007/bf01700692 · Cited by 2,395
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Gödel, K. (2006) · Monatshefte für Mathematik · doi:10.1007/s00605-006-0423-7 · Cited by 2,077
An Unsolvable Problem of Elementary Number Theory
Church, A. (1936) · American Journal of Mathematics · doi:10.2307/2371045 · Cited by 1,763
Recursively enumerable sets of positive integers and their decision problems
Post, E. L. (1944) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1944-08111-1 · Cited by 872 · cited 1×
“We assume familiarity with a paper of Kleene [5](2), and with ideas which are well summarized in the first sections of a paper of Post [7].”
MethodOn Notation for Ordinal Numbers
Kleene, S. C. (1938) · Journal of Symbolic Logic · doi:10.2307/2267778 · Cited by 758 · cited 1×
“That is, A includes XI*-o L(a,)- (In fact, it can be shown(4) that the finite sets of A can be recursively enumerated, so that A includes the EIX^ class generated by its finite sets.”
BackgroundGeneral recursive functions of natural numbers
Kleene, S. C. (1936) · Mathematische Annalen · doi:10.1007/bf01565439 · Cited by 593
Recursive predicates and quantifiers
Kleene, S. C. (1943) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1943-0007371-8 · Cited by 363
Extensions of some theorems of Gödel and Church
Rosser, B. (1936) · Journal of Symbolic Logic · doi:10.2307/2269028 · Cited by 359
Bernays, P. (1937) · Journal of Symbolic Logic · doi:10.2307/2268833 · Cited by 205
On definable sets of positive integers
Mostowski, A. (1947) · Fundamenta Mathematicae · doi:10.4064/fm-34-1-81-112 · Cited by 77
Cited by
Recursively Enumerable Sets and Degrees
Soare, R. I. (1987) · Perspectives in mathematical logic · doi:10.1007/978-3-662-02460-7 · Cited by 1,546
Inductive Logic Programming: Theory and methods
Muggleton, S., & de Raedt, L. (1994) · The Journal of Logic Programming · doi:10.1016/0743-1066(94)90035-3 · Cited by 1,537
“Stahl's proof is based on an application of Rice's Theorem [117] on the undecidability of non-trivial index sets being recursively enumerable.”
MethodRecursively enumerable sets and degrees
Soare, R. I. (1978) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1978-14552-2 · Cited by 1,520
Modeling and Discovering Vulnerabilities with Code Property Graphs
Yamaguchi, F., Golde, N., Arp, D., & Rieck, K. (2014) · 2014 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2014.44 · Cited by 808
“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].”
BackgroundAbandoning Objectives: Evolution Through the Search for Novelty Alone
Lehman, J., & Stanley, K. O. (2011) · Evolutionary Computation · doi:10.1162/evco_a_00025 · Cited by 917
“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).”
Background
Metadata
- Authors
- Rice, H. G.
- Corresponding author
- Rice, H. G.
- Venue
- Transactions of the American Mathematical Society
- Publisher
- American Mathematical Society (AMS)
- Published
- 1953
- Volume
- 74
- Issue
- 2
- Pages
- 358-366
- ISSN
- 0002-9947 (ISSN-L)
- 1088-6850
- OpenAlex
- W2047764386
- Cited by
- 869
- References
- 14
- Citations by year
- 2026: 48 · 2025: 48 · 2024: 47 · 2023: 37 · 2022: 32 · 2021: 59 · 2020: 42 · 2019: 38 · 2018: 35 · 2017: 38 · 2016: 34 · 2015: 34 · 2014: 24 · 2013: 25 · 2012: 25
- FWCI
- 7.38
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Transactions of the American Mathematical Society (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Mathematics › Geometry and Topology › Advanced Topology and Set Theory
- Keywords
- computably enumerable sets, decision problems, computability theory, Turing degrees
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Classes of recursively enumerable sets and their decision problems. https://app.cochat.ai/papers/10.1090/s0002-9947-1953-0053041-6
- The paper
- Rice, H. G. (1953). Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society. https://doi.org/10.1090/s0002-9947-1953-0053041-6
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.