For an effective enumeration of unary partial computable functions, the diagonal halting set is
Equivalently, for an enumeration of computably enumerable sets, .
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.
If , then
differs from , while the computable map proves .
The set is also a computably enumerable set, so the many-one completeness of the halting problem gives . Together the two many-one reductions place and in the same many-one degree.

Ancestors (7)

  1. Halting problem
  2. Recursively enumerable language
  3. Formal language theory
  4. Foundations of mathematics
  5. Area of mathematics
  6. Mathematics
  7. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.