Recursively Enumerable Sets of Positive Integers and Their Decision Problems

Post, E. L. (1944). Recursively Enumerable Sets of Positive Integers and Their Decision Problems. Bulletin of the American Mathematical Society, 50(5), 284-316.

Type

Journal article

Intellectual base

Primary research

Year

1944

Volume

50

Issue

5

Pages

284-316

ISSN

0002-9904

DOI

10.1090/s0002-9904-1944-08111-1

DOI registrant

American Mathematical Society

Link

https://doi.org/10.1090/S0002-9904-1944-08111-1

Cited from

computer_science

Cited by

3 citations across 3 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Computability
  • with the take-away that any sufficiently expressive procedural system can pose questions about itself it cannot answer. Degrees of unsolvability: the uncomputable problems are not all equally unsolvable but form a hierarchy (the Turing degrees, the arithmetical hierarchy) ordered by relative computability

    This sourceInitiates the theory of degrees of unsolvability (Turing degrees), giving the unsolvable region internal structure ordered by relative computability.

Domain-specific

• Reduction (Computability Theory)
  • Reductions compare undecidable sets, define Turing degrees and finer degree structures, prove noncomputability, classify computably enumerable sets, formulate completeness, and analyze jumps and hierarchies.
• Truth-table reduction
  • A set \(A\) is truth-table reducible to \(B\), written \(A\leq_{tt}B\), when one effective total procedure maps each input \(x\) to finitely many queries about \(B\) and a Boolean function such that the function of those simultaneously determined answer bits equals the characteristic value of \(A(x)\).

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Not recorded. Neither this nor any other of the 3 citations of this work carries a recorded support check.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:155db4398e61 · see in the full table