---
title: "Absolutely Unsolvable Problems and Relatively Undecidable Propositions"
authors:
  - "Emil L. Post"
year: 1965
venue: "In Davis (ed.), The Undecidable (account of 1941 work)"
arxiv: null
doi: null
source: "https://archive.org/details/undecidablebasic0000mart"
topics:
  - post
  - undecidability
  - incompleteness
seed_rank: 536
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 8
lineage: foundations-of-computing
cites:
  - title: "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I"
    url: "https://doi.org/10.1007/BF01700692"
    year: 1931
    arxiv: null
    doi: "10.1007/BF01700692"
  - 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: "An Unsolvable Problem of Elementary Number Theory"
    url: "https://doi.org/10.2307/2371045"
    year: 1936
    arxiv: null
    doi: "10.2307/2371045"
  - title: "The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions"
    url: "https://archive.org/details/undecidablebasic0000mart"
    year: 1965
    arxiv: null
    doi: null
see:
  - "500-uber-formal-unentscheidbare-satze-der-principia-mathematica-"
  - "534-recursively-enumerable-sets-of-positive-integers-and-their-d"
  - "507-an-unsolvable-problem-of-elementary-number-theory"
  - "636-the-undecidable-basic-papers-on-undecidable-propositions-uns"
---

# Absolutely Unsolvable Problems and Relatively Undecidable Propositions

## One-sentence takeaway

Post's unpublished 1941 analysis separates *absolute* unsolvability (no algorithm exists, period) from *relative* undecidability (a sentence independent of a given formal system)—the conceptual hygiene that keeps Gödel from being confused with Church–Turing.

## Why it matters here

Broadside's epistemology spine needs this distinction every time someone says a standing rule, type, or simulation axiom is "undecidable." Incomplete-for-this-theory is not the same as uncomputable-for-any-machine; Post wrote the memo that says so.

## Key ideas

- Written around 1941; first published in Martin Davis, *The Undecidable* (Raven Press, 1965).
- Absolute unsolvability is a fact about effective procedures; relative undecidability is a fact about a particular axiom system.
- Records Post's independent path toward incompleteness-style insights, in the production-system vocabulary of his other papers.
- Pair with the 1944 r.e.-sets address: that paper is the public theorem, this one is the private conceptual cleanup.

## Caveats

## Links

- Davis anthology: https://archive.org/details/undecidablebasic0000mart