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

DOI

10.1090/s0002-9904-1944-08111-1

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

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

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