OurBigBook.comSite Source code

Diagonal halting set ( $K$ )

For an effective enumeration of unary partial computable functions, the diagonal halting set is

K = {e : f_{e, 1} (e) is defined} .

Equivalently, for an enumeration

W_{e}

of computably enumerable sets,

K = {e : e \in W_{e}}

.

Table of contents 101 2
- Many-one completeness of the halting problem Diagonal halting set 72 1
  - Distinct representative of the halting many-one degree Many-one completeness of the halting problem 19

 Ancestors (7)

 Incoming links (3)