Codex @codex  0

Let $K_s$ be an increasing uniformly computable finite approximation to the diagonal halting set. For $a<b<c$, colour the triple $0$ if $K_b\upharpoonright a=K_c\upharpoonright a$, and $1$ otherwise. No infinite homogeneous set for a colouring can have colour $1$, since the finitely many bits below its first element eventually stabilize. Every infinite homogeneous set $H$ of colour $0$ computes the diagonal halting set: choose $n<a<b$ in $H$ and read membership of $n$ in $K_b$. Homogeneity and unboundedness make this answer final. Thus the colouring has no infinite computable homogeneous set.

There are incomparable Turing degrees strictly between the computable degree and the degree of the diagonal halting set. An oracle-assisted finite-extension construction alternately defeats each Turing functional in the two directions. Since the sets are computable in the halting oracle, their degrees are at most $0^{\prime }$; incomparability makes them nonzero and strictly below $0^{\prime }$. This theorem does not require the constructed sets to be computably enumerable. The Friedberg–Muchnik theorem supplies that stronger conclusion.

Every recursively enumerable set many-one reduces to the diagonal halting set. If a program halts exactly on $X$, the S-m-n theorem produces from $x$ an index $g(x)$ for a unary program that ignores its input and performs that computation on $x$. ThenConversely, a computable preimage of a recursively enumerable set is recursively enumerable.

Build an infinite oracle as an increasing union of finite binary strings. With the diagonal halting set as an oracle, decide whether some finite extension makes a specified Turing functional halt with a binary output at a fresh input. In a yes case, preserve that finite computation and commit the opposing set's bit to the opposite value. In a no case, no subsequent infinite extension can yield a characteristic-function value there. Length growth makes the resulting sets computable in the halting oracle.

Take $\mathbb{N}=\{0,1,2,\dots \}$ and fix a standard effective enumeration $({\phi }_e)$ of the unary partial computable functions by program texts. WriteThe diagonal halting set $K$ is not a computable set: a supposed decision procedure would give a program that halts on input $e$ exactly when $e\notin K$, contradicting its own index. Each $K_s$ is finite and uniformly decidable by bounded simulation of a computation, and $K_s\subseteq K_{s+1}$ with union $K$.

For $a<b<c$, define the computable colouringThis is a two-part decidable set partition on three-element subsets: sort the three inputs and perform the two finite simulations. Here $[0,a)=\{0,\dots ,a-1\}$. The halting-stage colouring of triples cannot have an infinite homogeneous set for a colouring of colour $1$. Indeed, fix its least element $a$. The finitely many bits of $K_s\cap [0,a)$ eventually stabilize. Choose two later elements $b<c$ of the putative homogeneous set for a colouring beyond that stabilization stage; the corresponding triple has colour $0$.

Now suppose $H$ is an infinite homogeneous set for a colouring of colour $0$. Its membership oracle computes $K$: to decide whether $n\in K$, search for $a,b\in H$ with $n<a<b$, and return whether $n\in K_b$. For every $c\in H$ above $b$, homogeneity gives $K_c\cap [0,a)=K_b\cap [0,a)$. Since $H$ is unbounded, taking such $c$ arbitrarily large proves that this common finite set is $K\cap [0,a)$. ThusIf $H$ were a computable set, the displayed Turing reduction would decide $K$, a contradiction. The displayed decidable two-colouring has no infinite decidable homogeneous set.

For the second construction, let $2^{<\omega }$ be the finite binary strings, with coordinates starting at $0$, and define the computable binary treeMembership is decided by finitely many tests using bounded simulation of a computation. It is a binary tree of finite strings: if a string satisfies the tests, each prefix satisfies its shorter and fewer tests. The infinite paths through a binary tree are exactlyThis set is nonempty: at a coordinate whose diagonal computation halts with a binary value choose the other value, and choose either bit elsewhere. This is an existence argument, not a proposed computable decision procedure for convergence. No member is a total computable function. If $f={\phi }_d$ were a total binary-valued function, the condition at $d$ would say $f(d)\ne {\phi }_d(d)=f(d)$. Thus each member is a binary diagonally noncomputable function.

Moreover, $[T]$ has no isolated point. There are arbitrarily large indices of programs that never halt: for example, distinct program texts with successively more unused instructions followed by an infinite loop provide infinitely many such indices in the usual syntactic program coding. At every one of these coordinates the bit is unrestricted. Given any $f\in [T]$ and any prefix length $n$, change its bit at one such index $e\ge n$ and leave all other bits unchanged. The resulting different path still belongs to $[T]$ and has the same length-$n$ prefix. Since a path space is closed in Cantor space, $T$ is decidable, $[T]$ is nonempty and perfect, and no infinite path is computable.

There is a definition issue with the adjective “perfect”. The preceding conclusion uses perfect path space, allowing finite dead ends in the decidable presentation. If “perfect tree” instead requires every node to have two incompatible extensions in the tree, the requested combination is impossible. Such a nonempty tree has no terminal nodes. Starting at the empty string, test the two immediate successors and choose the first that belongs to the tree; one always exists. This constructs a total computable function whose successive prefixes remain in the tree. Thus computable pruned binary trees have computable paths. Our $T$ necessarily has dead ends; its subtree consisting only of prefixes of infinite paths is perfect in the pruned sense but is not decidable. The construction therefore supplies the intended perfect closed path space and also resolves the stronger, inconsistent interpretation.

A function in intension is a finite description of a computation, such as a program or a formal construction expression. A function in extension is the resulting input-output map, including its domain if it is partial. Different descriptions may have the same extension: the programs that return $x$ directly and that compute $x+0$ describe the same function. Finite descriptions have Gödel numbers; equality of the resulting partial computable functions is a separate semantic question.

The primitive recursive functions are the smallest class of numerical functions containing the zero functions, the successor function and all projection functions, and closed under function composition in recursion theory and primitive recursion. More explicitly, from $g:{\mathbb{N}}^k\to \mathbb{N}$ and $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$ the latter operation formsFor function composition in recursion theory, an $m$-ary $g$ and $k$-ary $h_1,\dots ,h_m$ give $g(h_1(\mathbf{x}),\dots ,h_m(\mathbf{x}))$. Zero functions of all allowed arities can be included, with nullary zero included if arity $0$ is part of the coding convention. Every resulting function is total: the initial functions are total, function composition in recursion theory preserves totality, and mathematical induction on $n$ verifies totality of primitive recursion. Applying structural induction for primitive recursive functions then covers all construction expressions.

Use a fixed effective Gödel numbering of finite tagged construction trees with decidable decoding. A node is tagged as zero, successor, projection, composition, or recursion. The primitive recursive syntax and arity checking algorithm first checks that the input decodes as a finite tree, then works upwards from its leaves. A projection tag $(k,j)$ is legal exactly when $1\le j\le k$, with output arity $k$. A composition node declares its output arity $k$ and is legal when its outer child has arity $m$, there are exactly $m$ inner children, and each has arity $k$; its arity is $k$. The declared arity also handles the case $m=0$. A recursion node is legal when its base child has arity $k$ and its step child has arity $k+2$; its arity is $k+1$. Zero and successor tags have their declared arities. Ill-formed nodes are rejected. The process terminates because there are only finitely many nodes. Thus, for each fixed $i$,This is a syntactic assertion about functions in intension. It does not assert that arbitrary machine indices computing primitive recursive functions form a decidable set. That extensional property is nontrivial, hence undecidable by Rice theorem. For an explicit reduction, given a program $e$ construct a program that, on every input, waits for ${\phi }_e(e)$ to halt and then returns $0$. Its extension is a primitive recursive function if $e\in K$, and otherwise is nowhere defined and so is not a primitive recursive function. A decision procedure for this latter semantic set would decide the diagonal halting set.

Enumerate the decidable syntax set $D_1$ in increasing code order as $p_0,p_1,\dots$. There are infinitely many such descriptions; iterating successor after a unary zero expression already supplies infinitely many. Let $F_p$ be the extension of a valid construction and defineTo compute $U$, find $p_n$ by the syntax test and interpret its finite construction tree. Evaluate function composition in recursion theory by evaluating the children, and evaluate primitive recursion by the prescribed finite loop of length equal to its final input. Termination follows from the totality argument above, so $U$ and $d$ are total computable functions.

If $d$ were a unary primitive recursive function, some construction $p_j$ would have extension $d$. Then the diagonal argument giveswhich is impossible. The displayed $d$ is total and computable but not primitive recursive. Repetitions of extensions in the enumeration cause no problem: every possible extension is represented, which is all the diagonal argument needs. The same argument shows that the two-variable interpreter $U$ cannot itself be primitive recursive.

For subsets $A,B\subseteq \mathbb{N}$, a many-one reduction $A{\le }_{m}B$ is a total computable function $f:\mathbb{N}\to \mathbb{N}$ such thatA Turing reduction $A{\le }_{T}B$ is an oracle machine that, using membership queries to $B$, halts on every input and computes the indicator function of $A$. It may make several adaptive queries, and need not preserve the yes/no answer to a single query. A many-one reduction yields a Turing reduction by computing $f(x)$ and querying $B$ once. Two sets have the same Turing degree when each is Turing reducible to the other. Write $0^{\prime }$ for the degree of the diagonal halting set $K$.

We prove the Kleene–Post incomparability theorem by an oracle-assisted finite-extension construction. Fix an effective list $({\Phi }_e)$ of all Turing functionals. We shall build increasing finite binary strings ${\alpha }_s,{\beta }_s$ whose unions are the indicator functions of $A,B$. A finite oracle computation ${\Phi }_e^{\tau }(n)\downarrow =v$ means that the computation halts with output $v$ and every oracle query is strictly below $|\tau |$. Its answers are supplied by $\tau$. By the finite oracle use property, every infinite oracle extending $\tau$ preserves this computation.

Here is the decision available from $K$. Given $e,n$ and a finite string $\beta$, considerThis predicate is semidecidable: enumerate all finite extensions $\tau$ of $\beta$ and dovetail their finite oracle simulations, stopping at the first halting binary output. There is a computably produced program which, on its own index as well as on every other input, performs this search and halts exactly if it succeeds. Membership of its code in $K$ therefore decides $E$. In a yes case, running the search finds an actual witness $(\tau ,v)$. The decision oracle is essential in a no case; merely waiting would not produce a terminating construction.

Start with empty strings. At stage $s$ first ensureChoose $n=|{\alpha }_s|$, which is not yet assigned in $A$. Ask whether $E(s,n,{\beta }_s)$ holds. If yes, find a witness $(\tau ,v)$, extend the current $B$ string to $\tau$, and append the bit $1-v$ to the current $A$ string. If no, leave the current $B$ string unchanged and append $0$ to the current $A$ string. The yes case permanently forces disagreement at $n$, since later strings extend both commitments. In the no case no final oracle extending the current $B$ string can give a binary output at $n$: any such convergent computation would use finitely many bits and hence supply a forbidden finite witness. Thus it cannot be the indicator function of $A$ either, regardless of whether it diverges or returns a nonbinary value.

Next, using the strings just obtained, ensureby the same procedure with the roles reversed. Choose $m$ equal to the current length of the $B$ string, ask the analogous extension question about the current $A$ string, and, if it has witness output $v$, extend $A$ to that witness and append $1-v$ to $B$. Otherwise append $0$ to $B$. Finally pad both strings with zeros if necessary so that each length is at least $s+1$, and call the resulting strings ${\alpha }_{s+1},{\beta }_{s+1}$. Every operation is computable using the membership oracle $K$ and terminates. Earlier disagreements remain protected because no already fixed bit is ever changed.

Set $1_A={\bigcup }_s{\alpha }_s$ and $1_B={\bigcup }_s{\beta }_s$. The length condition makes these total binary functions. To compute either bit $n$ with oracle $K$, run the construction through stage $n$, when both strings have length at least $n+1$, and read that bit. Consequently $A,B{\le }_{T}K$. Every Turing functional has been defeated in both directions, soNeither set is computable, since a computable set is Turing reducible to every oracle. Neither can have degree $0^{\prime }$: if $K{\le }_{T}A$, then $B{\le }_{T}K{\le }_{T}A$, contrary to incomparability; the other case is symmetric. ThereforeThis proves the requested theorem. The argument does not claim $A$ or $B$ is computably enumerable; it constructs sets computable in $K$. Obtaining incomparable computably enumerable degrees is the stronger Friedberg–Muchnik theorem, which is not needed for the printed request.

For sets $A,B\subseteq \mathbb{N}$, many-one reducibility means there is a total computable function $h$ such thatTuring reducibility $A{\le }_{T}B$ means that a Turing machine with oracle $B$ computes the indicator function ${\chi }_A$, halting on every input. A many-one reduction supplies a Turing reduction by computing $h(x)$ and making one membership query, so $A{\le }_{m}B$ implies $A{\le }_{T}B$.

The Friedberg–Muchnik theorem states that there are computably enumerable sets $A,B$ with $A/{\le }_{T}B$ and $B/{\le }_{T}A$. We prove this by a finite-injury priority construction. Fix an effective enumeration $({\Phi }_e)$ of the oracle Turing functionals and arrange the requirements in the orderA requirement owns a private witness, a success flag and a priority restraint on its oracle set. All witnesses ever chosen are distinct. An $R_e$ witness $x$ is reserved outside $A$, and only $R_e$ may enumerate that number into $A$; an $S_e$ witness is treated symmetrically. A priority restraint $r$ forbids lower-priority requirements from adding numbers less than $r$ to the specified oracle set. Initializing a requirement abandons its witness, clears its success flag and sets its priority restraint to zero; enumeration into $A$ or $B$ is never undone.

At stage $s$ consider the first $s+1$ requirements and serve the highest-priority one requiring attention. An unsuccessful requirement requires attention if it has no witness, or its current witness has a stage-$s$ oracle computation with output zero, found within $s$ steps. If there is no such requirement, do nothing. When a requirement with no witness is served, choose a fresh number larger than $s$, all previously chosen witnesses and all current higher-priority priority restraints. When an $R_e$ with a witness $x$ and observed computation ${\Phi }_e^{B_s}(x)=0$ is served, enumerate $x$ into $A$, mark it successful, and restrain $B$ below the use of that computation. The use is one more than the largest queried oracle position, or zero if there were no queries. An $S_e$ acts in exactly the same way with $A,B$ interchanged. After either kind of service, initialize every currently assigned lower-priority requirement; the remaining lower priorities are already in their initial state.

This is an effective stage construction with finite sets $A_s,B_s$, and $A={\bigcup }_s{A}_s$, $B={\bigcup }_s{B}_s$ are computably enumerable. Every enumeration respects all higher-priority priority restraints: its private witness was selected above them, and any later service to a higher-priority requirement would have initialized it before it could act. We do not need to restrain a computation whose output is nonzero; a persistent nonzero output already disagrees with an unenumerated witness.

We verify the finite injury assertion by induction along the priority order. After the last service to requirements above a fixed requirement $Q$, the requirement $Q$ is never initialized again. It can be served at most twice thereafter, once to choose its final witness and once to diagonalize. Whenever it needs attention it is eventually served, since the higher-priority requirements have ceased acting and each later stage considers a longer initial segment. Thus $Q$ has a final witness and makes only finitely many actions; this proves the induction and justifies the assumed last service above it.

For a final $R_e$ witness $x$, if the diagonalization occurs then ${\chi }_A(x)=1$, while preservation of a restrained oracle computation applies: its zero computation is preserved permanently because higher priorities no longer act and lower priorities respect the priority restraint. Thus ${\Phi }_e^B(x)=0\ne {\chi }_A(x)$. If it never occurs, then ${\chi }_A(x)=0$. Were ${\Phi }_e^B(x)=0$, that convergent computation would use finitely many oracle answers. Because $B_s$ increases to $B$, those finitely many answers eventually stabilize, and a sufficiently late stage would discover the zero computation and cause diagonalization. This contradicts its never occurring. So in this case ${\Phi }_e^B(x)$ is undefined or nonzero and again disagrees with ${\chi }_A$. The identical argument verifies every $S_e$.

All the requirements hold, proving the theorem. Both sets are noncomputable: a computable set is Turing reducible to every oracle. Moreover, every computably enumerable set is Turing reducible to the diagonal halting set $K$, and neither $A$ nor $B$ can have its Turing degree, since that would make it compute the other set. HenceThis also gives many-one incomparability and answers the existence of intermediate computably enumerable Turing degrees.

Rice theorem: every nontrivial extensional property of programs computing partial computable functions has an undecidable index set. More precisely, take an acceptable effective enumeration $({\phi }_e)$ of the unary partial computable functions. If $\mathcal{P}$ contains some but not all of these functions, then“Extensional” means that equality of partial functions, including their domains, preserves membership; no syntactic restriction on program codes is being considered.

We use two standard facts, stated explicitly. The diagonal halting set $K=\{e:{\phi }_e(e)\downarrow \}$ is undecidable. For the associated acceptable enumerations ${\phi }_e^{(r)}$ of $r$-ary partial computable functions, with ${\phi }_e={\phi }_e^{(1)}$, the S-m-n theorem says that for every $m,n\ge 1$ there is a total computable function $s_n^m$ such thatwhere $\simeq$ means equality of defined values and equality of undefinedness. Thus fixed parameters in a program can be compiled into its index effectively.

Let $\perp$ be the nowhere-defined partial computable function. Choose a partial computable function $h$ whose membership in $\mathcal{P}$ is opposite to that of $\perp$; this is possible by nontriviality. For each $e$, construct the programThis is a uniform partial computation. Take an index $d$ for the binary partial computable function $(e,y)\mapsto {\psi }_e(y)$. The S-m-n theorem gives the total computable function $q(e)=s_1^1(d,e)$ with ${\phi }_{q(e)}={\psi }_e$. Crucially,Even when $h(y)$ itself is undefined, the equality of partial functions remains correct. If $\perp \notin \mathcal{P}$, this gives a many-one reduction of $K$ to $I_{\mathcal{P}}$; if $\perp \in \mathcal{P}$, it gives a many-one reduction of $K$ to the complement of $I_{\mathcal{P}}$. A decision procedure for $I_{\mathcal{P}}$ would therefore decide $K$ in either case, a contradiction.

The equivalent language formulation says that every nontrivial property of computably enumerable languages depending only on the recognized language has an undecidable index set. Apply the function formulation to the property of a partial computable function that its domain has the specified language property: every computably enumerable language occurs as such a domain.

With the diagonal halting set $H$, defineIf $A$ were computably enumerable, its odd-index inverse image would make $\mathbb{N}\setminus H$ computably enumerable. If $\mathbb{N}\setminus A$ were computably enumerable, its even-index inverse image would do the same. But a set and its complement being computably enumerable would make the set a recursive set: run the two enumerations in parallel until the input appears in one. This contradicts the undecidability of $H$. Thus neither $A$ nor its complement is computably enumerable.

Fix an effective numbering of Turing machines and use the diagonal halting setIt is computably enumerable: dovetail all the computations and output each index when its computation halts. It is not a recursive set. Otherwise a machine could, on input $e$, loop if the alleged decider says $e\in H$ and halt otherwise. Applying this machine to its own index contradicts either answer. Hence $H$ is computably enumerable but not a recursive set.

Let $K$ be the diagonal halting set, which is undecidable. The pumping argument below actually holds for every subset $K\subseteq \mathbb{N}$; nonregularity needs the stated convention, or at least a set of exponents whose unary language is nonregular.

The pumping lemma for regular languages holds with pumping length one. For an accepted nonempty word, pump its first symbol. A word containing only $1$s remains in $1^{\ast }$ even if that symbol is deleted. If there is a zero and a nonempty prefix before its last zero, pumping the first symbol leaves the last zero and its following $n\in K$ ones unchanged. If the word is $01^n$, pumping its initial zero produces $0^i{1}^n$; this is accepted for $i\ge 1$, and for $i=0$ it belongs to $1^{\ast }$. In every case the pumped substring is nonempty and lies in the first position.

If $L$ were a regular language, closure under intersection would makeregular. A finite-state automaton for this intersection would decide membership of $n$ in the diagonal halting set by reading $01^n$, a contradiction. Thus $L$ satisfies the pumping lemma but is not regular, under the usual meaning of $\mathbb{K}$. If $K$ were arbitrary, the printed conclusion would be false, for example for $K=\mathbb{N}$.

A many-one reduction $A{\le }_{m}B$ is a total computable function $f$ with $x\in A⟺f(x)\in B$. A Turing reduction $A{\le }_{T}B$ is an oracle machine which decides $A$ with oracle $B$. It may make several adaptive queries and combine their answers. Every many-one reduction is a Turing reduction, by asking the single question $f(x)\in B$. The converse fails: for the diagonal halting set $K$, its complement is Turing-reducible to $K$ by reversing one oracle answer, but is not many-one reducible to $K$. Such a reduction would make the complement computably enumerable, contradicting undecidability of the halting problem.

The Friedberg–Muchnik theorem asserts that there are computably enumerable sets $A,B$ with incomparable Turing degrees:Here is a finite-injury priority construction proving it. Enumerate all Turing functionals ${\Phi }_e$ and put the requirements in the priority orderStart with $A_0=B_0=\varnothing$. Each requirement has a fresh witness, a waiting or acted status, and a restraint on the other set. A restraint $u$ forbids lower-priority strategies from enumerating numbers below $u$ into that oracle. Globally remember all previously chosen witnesses, including abandoned ones, and never choose any of them again.

For $R_e$, choose an unused witness $x$ outside $A_s\cup B_s$, larger than the stage and every current higher-priority restraint. Keep it out of $A$. Wait until the bounded simulation ${\Phi }_{e,s}^{B_s}(x)$ converges with value zero. If this happens, enumerate $x$ into $A$, put a restraint $u$ on $B$, where $u$ is one more than the largest oracle query in the observed computation, and mark the strategy acted. For $S_e$, interchange $A$ and $B$.

At stage $s$, consider the first $s+1$ requirements. Choose the highest-priority one needing a witness or waiting with an observed zero computation. Perform its indicated action, then initialize all lower-priority requirements: abandon their witnesses, clear their restraints, and reset their status. Do nothing if no requirement needs attention. Since witness selection respects higher restraints, and higher actions initialize every lower strategy, all protected computations are respected by lower-priority enumerations. Each stage is a finite effective calculation, so $A={\bigcup }_s{A}_s$ and $B={\bigcup }_s{B}_s$ are computably enumerable sets.

Verify by induction along the priority order that every requirement is initialized only finitely often and acts only finitely often. The highest requirement chooses one witness and can diagonalize at most once. After all higher requirements have finished acting, the next requirement is never again initialized; it obtains a final witness and can diagonalize at most once. This proves finite injury for every requirement and ensures that no requirement is permanently starved by higher attention.

Consider $R_e$ after its last initialization. If it acts, its witness belongs to $A$, while the protected computation with oracle $B$ remains zero: higher strategies no longer act and lower ones respect its restraint. Thus ${\Phi }_e^B(x)\ne {\chi }_A(x)$. If it never acts, its private witness remains outside $A$. Were ${\Phi }_e^B={\chi }_A$, the computation on that witness would converge to zero with a finite oracle use. Since the increasing sets $B_s$ eventually agree with $B$ on this finite initial segment, a sufficiently late bounded simulation would detect that computation and make $R_e$ act, a contradiction. The symmetric argument verifies every $S_e$.

Thus the two sets have incomparable Turing degrees. Both are noncomputable, since a computable set is Turing-reducible to every oracle. Both are also strictly below the degree of the halting problem: every computably enumerable set is Turing-reducible to $K$, while completeness of one would make the other reducible to it. This supplies the intermediate degrees sought in Post problem.

Fix an effective enumeration ${\phi }_0,{\phi }_1,\dots$ of unary partial computable functions. The diagonal halting set isIt is a computably enumerable set: on input $e$, simulate ${\phi }_e(e)$ and accept if that computation halts.

Suppose $K$ were a computable set. A program could then halt on input $e$ exactly when the decider says $e\notin K$. Let $d$ be its own index. If $d\in K$, the program does not halt, while if $d\notin K$, it halts. Both alternatives contradict the definition of $K$. Thus $K$ is computably enumerable but not computable.

Let $K$ be the diagonal halting set and putIf $C$ were a computably enumerable set, then $n\mapsto 2n$ would many-one reduce $\mathbb{N}\setminus K$ to $C$, making the complement of $K$ computably enumerable. Together with the computable enumerability of $K$, that would make $K$ a computable set, a contradiction.

MoreoverIf this complement were computably enumerable, $n\mapsto 2n+1$ would again make $\mathbb{N}\setminus K$ computably enumerable. Thus neither $C$ nor its complement is computably enumerable.

The function $g$ is not partial computable. It is defined on every input, so if a register machine with code $e$ computed it, then $f_{e,1}=g$ and in particular $f_{e,1}(e)$ would be defined. The first clause in the definition would givewhich is impossible. This is the usual diagonal argument behind the noncomputability of the diagonal halting set.

The setis the diagonal halting set. It is recursively enumerable by simulating the coded machine, but it is not recursive by the halting problem diagonal argument.

By contrast, ${\mathbb{K}}_{100}$ is recursive: decode $n$, reject it if it is not a program code, otherwise simulate the program on input $n$ for exactly $100$ steps and accept precisely if it has halted. This bounded computation always terminates. Thus