---
title: "Degrees of Recursive Unsolvability"
authors:
  - "Stephen C. Kleene"
  - "Emil L. Post"
year: 1954
venue: "Annals of Mathematics"
arxiv: null
doi: "10.2307/1969708"
source: "https://doi.org/10.2307/1969708"
topics:
  - turing-degrees
  - kleene
  - post
  - computability
seed_rank: 539
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 9
lineage: foundations-of-computing
cites:
  - title: "Recursively enumerable sets of positive integers and their decision problems"
    url: "https://doi.org/10.1090/S0002-9904-1944-08111-1"
    year: 1944
    arxiv: null
    doi: "10.1090/S0002-9904-1944-08111-1"
  - 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
  - title: "Recursive predicates and quantifiers"
    url: "https://doi.org/10.1090/S0002-9947-1943-0007371-8"
    year: 1943
    arxiv: null
    doi: "10.1090/S0002-9947-1943-0007371-8"
see:
  - "534-recursively-enumerable-sets-of-positive-integers-and-their-d"
  - "540-two-recursively-enumerable-sets-of-incomparable-degrees-of-u"
  - "541-on-the-unsolvability-of-the-problem-of-reducibility-of-the-t"
  - "528-recursive-predicates-and-quantifiers"
---

# Degrees of Recursive Unsolvability

## One-sentence takeaway

Kleene and Post construct incomparable Turing degrees below \(0'\) by finite extension, showing the degree universe is already rich before anyone solves Post's r.e. problem.

## Why it matters here

Method ancestor of every later priority construction. When Broadside talks about "structure inside undecidability," this is the first paper that *builds* incomparable degrees rather than merely defining reducibility.

## Key ideas

- A Turing degree is an equivalence class of sets under mutual Turing reducibility.
- Finite-extension (forcing-style) constructions produce sets \(A, B \leq_T 0'\) with \(A \nleq_T B\) and \(B \nleq_T A\).
- The constructed degrees need not be r.e.; Post's problem (incomparable *r.e.* degrees) remains open here and is solved by Friedberg–Muchnik.
- Sets the combinatorial pattern—meet requirements one by one, injuring earlier ones only finitely often—that priority methods will refine.

## Caveats

## Links

- DOI: [10.2307/1969708](https://doi.org/10.2307/1969708)
- JSTOR: https://www.jstor.org/stable/1969708