---
title: "On the unsolvability of the problem of reducibility of the theory of algorithms"
authors:
  - "A. A. Muchnik"
year: 1956
venue: "Doklady Akademii Nauk SSSR"
arxiv: null
doi: null
source: "https://www.mathnet.ru/rus/person46479"
topics:
  - priority-method
  - post-problem
  - degrees
  - muchnik
seed_rank: 541
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: "Degrees of Recursive Unsolvability"
    url: "https://doi.org/10.2307/1969708"
    year: 1954
    arxiv: null
    doi: "10.2307/1969708"
see:
  - "534-recursively-enumerable-sets-of-positive-integers-and-their-d"
  - "540-two-recursively-enumerable-sets-of-incomparable-degrees-of-u"
  - "539-degrees-of-recursive-unsolvability"
---

# On the unsolvability of the problem of reducibility of the theory of algorithms

## One-sentence takeaway

Muchnik independently solves Post's problem in the USSR: there is no single r.e. complete set to which every unsolvable r.e. problem reduces, because incomparable r.e. degrees exist.

## Why it matters here

Pair with Friedberg: completeness of the 1956–57 priority moment. Broadside should cite both when it says "undecidable problems are not all equivalent." The Russian-school packaging (Markov's theory of algorithms, Doklady note) is the other half of the same theorem.

## Key ideas

- Original: А. А. Мучник, «Неразрешимость проблемы сводимости теории алгоритмов», *Доклады АН СССР* 108:2 (1956), 194–197. No DOI; Math-Net author page is the stable landing.
- Shows there is no universal unsolvable r.e. problem: some r.e. sets do not Turing-reduce to others.
- Independent of Friedberg's PNAS note; together they are the Friedberg–Muchnik theorem.
- Followed by Muchnik's longer 1958 *Izvestiya* paper that develops the priority method in full.

## Caveats

## Links

- Math-Net author record: https://www.mathnet.ru/rus/person46479
- Bibliographic form: Dokl. Akad. Nauk SSSR 108 (1956), no. 2, 194–197