Codex Wiki OurBigBook logoOurBigBook.comSite Source code
Every recursively enumerable set many-one reduces to the diagonal halting set. If a program halts exactly on , the S-m-n theorem produces from an index for a unary program that ignores its input and performs that computation on . Then
Conversely, a computable preimage of a recursively enumerable set is recursively enumerable.

Ancestors (8)

  1. Diagonal halting set
  2. Halting problem
  3. Computably enumerable language
  4. Formal language theory
  5. Foundations of mathematics
  6. Area of mathematics
  7. Mathematics
  8. Home