---
title: "Recursively enumerable sets of positive integers and their decision problems"
authors:
  - "Emil L. Post"
year: 1944
venue: "Bulletin of the American Mathematical Society"
arxiv: null
doi: "10.1090/S0002-9904-1944-08111-1"
source: "https://doi.org/10.1090/S0002-9904-1944-08111-1"
topics:
  - re-sets
  - post
  - degrees
  - computability
seed_rank: 534
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 10
lineage: foundations-of-computing
cites:
  - title: "Finite Combinatory Processes—Formulation I"
    url: "https://doi.org/10.2307/2268534"
    year: 1936
    arxiv: null
    doi: "10.2307/2268534"
  - title: "Degrees of Recursive Unsolvability"
    url: "https://doi.org/10.2307/1969708"
    year: 1954
    arxiv: null
    doi: "10.2307/1969708"
  - title: "Two recursively enumerable sets of incomparable degrees of unsolvability"
    url: "https://doi.org/10.1073/pnas.43.2.236"
    year: 1957
    arxiv: null
    doi: "10.1073/pnas.43.2.236"
  - title: "On the unsolvability of the problem of reducibility of the theory of algorithms"
    url: "https://www.mathnet.ru/rus/person46479"
    year: 1956
    arxiv: null
    doi: null
see:
  - "532-finite-combinatory-processes-formulation-i"
  - "539-degrees-of-recursive-unsolvability"
  - "540-two-recursively-enumerable-sets-of-incomparable-degrees-of-u"
  - "541-on-the-unsolvability-of-the-problem-of-reducibility-of-the-t"
---

# Recursively enumerable sets of positive integers and their decision problems

## One-sentence takeaway

Post classifies r.e. sets (creative, simple, hypersimple) and asks whether there is an incomplete non-recursive r.e. degree—the question that launches degree theory.

## Why it matters here

Shows undecidability is not a boolean. When Broadside talks about "structure inside the unsolvable" or about reductions between agent-search problems, it is using the landscape this address opened.

## Key ideas

- Recursively enumerable sets are those generated by a finite process; their complements need not be.
- *Creative* sets (the halting problem is the prototype) are m-complete among r.e. sets; *simple* sets are r.e. with an immune complement, hence non-recursive but not complete in the obvious way.
- Post's problem: is there an r.e. set that is neither recursive nor complete? Left open here; solved by Friedberg and Muchnik in 1956–57.
- Founding paper of Turing-degree theory as a subject, not merely a definition.

## Caveats

## Links

- DOI: [10.1090/S0002-9904-1944-08111-1](https://doi.org/10.1090/S0002-9904-1944-08111-1)
- URL: https://doi.org/10.1090/S0002-9904-1944-08111-1