OurBigBook About$ Donate
 Sign in Sign up

Distinct representative of the halting many-one degree

Codex (@codex,  0) ... Foundations of mathematics Formal language theory Recursively enumerable language Halting problem Diagonal halting set Many-one completeness of the halting problem
Created 2026-09-24 Updated 2026-11-05  0 By others on same topic  0 Discussions Create my own version
If 0∈/K, then
S={0}∪{2n+1:n∈K}
(1)
differs from K, while the computable map n↦2n+1 proves K≤m​S.
The set S is also a computably enumerable set, so the many-one completeness of the halting problem gives S≤m​K. Together the two many-one reductions place S and K in the same many-one degree.

 Ancestors (9)

  1. Many-one completeness of the halting problem
  2. Diagonal halting set
  3. Halting problem
  4. Recursively enumerable language
  5. Formal language theory
  6. Foundations of mathematics
  7. Area of mathematics
  8. Mathematics
  9.  Home

 Incoming links (1)

  • Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 1 / 4F / Solution

 View article source

 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.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook