[proofplan] We construct $A$ by a finite-injury movable-marker argument. The markers $\gamma(n,s)$ are kept outside the current finite approximation $A_s$ and are moved whenever they must record a new entry into $K$ or when a simplicity requirement needs to use an unprotected marker. Each marker is injured only finitely many times, so the limiting marker positions form an infinite subset of $\omega \setminus A$. The same construction meets every requirement $R_e: W_e$ infinite $\implies W_e \cap A \neq \varnothing$, and the final marker positions allow an oracle for $A$ to decide $K$. [/proofplan] [step:Fix effective approximations and state the requirements] Let $\omega=\{0,1,2,\dots\}$. Fix computable increasing finite approximations $(K_s)_{s \in \omega}$ and $(W_{e,s})_{e,s \in \omega}$ such that \begin{align*} K &= \bigcup_{s=0}^{\infty} K_s, & W_e &= \bigcup_{s=0}^{\infty} W_{e,s} \end{align*} for every $e \in \omega$, where at each stage only finitely many new numbers enter the displayed finite sets. We build a computable increasing sequence of finite sets $(A_s)_{s \in \omega}$ and put \begin{align*} A := \bigcup_{s=0}^{\infty} A_s. \end{align*} For each $e \in \omega$, the simplicity requirement is \begin{align*} R_e:\qquad W_e \text{ is infinite } \implies W_e \cap A \neq \varnothing. \end{align*} At stage $s$, for each $n \leq s$ we maintain a marker $\gamma(n,s) \in \omega$ such that \begin{align*} \gamma(0,s) < \gamma(1,s) < \cdots < \gamma(s,s) \end{align*} and $\gamma(n,s) \notin A_s$ for every $n \leq s$. A marker $\gamma(n,s)$ is said to be protected for requirement $R_e$ at stage $s$ when $n \leq e$. [/step] [step:Define the movable-marker construction] Set $A_0=\varnothing$ and choose $\gamma(n,0)=n$ for the markers defined at stage $0$. More generally, whenever fresh markers are needed at a later stage, choose the least available numbers larger than every number so far mentioned in the construction and outside the current approximation to $A$, preserving the increasing order. Suppose $A_s$ and $\gamma(n,s)$ for $n \leq s$ have been defined. First extend the marker list, if necessary, by adding fresh markers until $\gamma(n,s)$ is defined for every $n \leq s+1$. Then perform the following finite actions. For every $n \leq s+1$ such that $n \in K_{s+1} \setminus K_s$, enumerate into $A$ all currently defined markers \begin{align*} \gamma(n,s),\gamma(n+1,s),\dots,\gamma(s+1,s), \end{align*} and replace exactly these markers by fresh larger markers, preserving the increasing order. Next consider the requirements $R_e$ with $e \leq s+1$ that have not yet acted. If there is an element \begin{align*} x \in W_{e,s+1} \end{align*} such that $x \notin A_s$ and \begin{align*} x \notin \{\gamma(0,s),\gamma(1,s),\dots,\gamma(e,s)\}, \end{align*} let $x$ be the least such element. If $x$ is not one of the currently defined markers, enumerate $x$ into $A$ and declare $R_e$ satisfied. If $x=\gamma(k,s)$ for some $k>e$, enumerate \begin{align*} \gamma(k,s),\gamma(k+1,s),\dots,\gamma(s+1,s) \end{align*} into $A$, replace exactly these markers by fresh larger markers, and declare $R_e$ satisfied. Let $A_{s+1}$ be the finite set obtained after all enumerations at stage $s+1$. Since each stage performs only finitely many computable searches and finite enumerations, the set $A$ is c.e. [/step] [step:Prove that every marker reaches a final value] Fix $n \in \omega$. We prove that the sequence $(\gamma(n,s))_{s \geq n}$ is eventually constant. A marker $\gamma(n,s)$ can be moved for two reasons. First, if some $m \leq n$ enters $K$, then the construction enumerates the tail of markers beginning at $\gamma(m,s)$, so $\gamma(n,s)$ is moved. There are only finitely many such $m$, namely $m \in \{0,\dots,n\}$, and each number enters the c.e. approximation to $K$ at most once. Second, a requirement $R_e$ can move $\gamma(n,s)$ only if $e \leq n$ and $R_e$ acts by choosing a marker $\gamma(k,s)$ with $e<k\leq n$. There are only finitely many such requirements $R_0,\dots,R_n$, and each requirement is declared satisfied after its first action and never acts again. Thus $\gamma(n,s)$ is moved only finitely many times. Hence there are a stage $s_n$ and a number $\gamma(n) \in \omega$ such that \begin{align*} \gamma(n,s)=\gamma(n) \end{align*} for every $s \geq s_n$. [guided] Fix one marker index $n$. The point is to list every possible source of injury to $\gamma(n,s)$ and check that the list is finite. The first possible source is the coding of $K$. If a number $m$ enters $K$ at a stage and $m \leq n$, then the construction enumerates the marker tail beginning at $\gamma(m,s)$, so the marker with index $n$ is included in that tail and must be replaced. If $m>n$, then the tail begins strictly after $\gamma(n,s)$, so $\gamma(n,s)$ is not affected. Therefore the only entries of $K$ that can injure $\gamma(n,s)$ are entries of numbers in the finite set $\{0,\dots,n\}$. Since each fixed number can enter the increasing approximation to $K$ at most once, this gives only finitely many injuries. The second possible source is a simplicity requirement. Requirement $R_e$ is forbidden to use any of the protected markers \begin{align*} \gamma(0,s),\gamma(1,s),\dots,\gamma(e,s). \end{align*} Thus, if $e>n$, then $\gamma(n,s)$ is protected from $R_e$ and cannot be moved by it. If $e \leq n$, then $R_e$ may move $\gamma(n,s)$ only in the case where it chooses some marker $\gamma(k,s)$ with $e<k\leq n$, because the construction then enumerates the tail beginning at $\gamma(k,s)$. There are only finitely many requirements $R_0,\dots,R_n$, and each one acts at most once. Combining the two finite lists, $\gamma(n,s)$ is moved only finitely many times. Therefore the sequence of values of the $n$th marker is eventually constant; denote its final value by $\gamma(n)$. [/guided] [/step] [step:Use the limiting markers to make the complement infinite] For each $n \in \omega$, the final marker value $\gamma(n)$ never enters $A$. Indeed, after stage $s_n$ the marker $\gamma(n,s)$ is never moved again, and the only way a current marker is enumerated into $A$ is as part of a marker-moving action. Hence $\gamma(n) \notin A$. Moreover the final markers are pairwise distinct. If $i<j$, then for every sufficiently large $s$ both $\gamma(i,s)$ and $\gamma(j,s)$ have stabilized, and the construction maintains \begin{align*} \gamma(i,s)<\gamma(j,s). \end{align*} Passing to the stable values gives \begin{align*} \gamma(i)<\gamma(j). \end{align*} Thus $\{\gamma(n):n \in \omega\}$ is an infinite subset of $\omega \setminus A$, so $\omega \setminus A$ is infinite. [/step] [step:Meet every simplicity requirement] Fix $e \in \omega$ and suppose $W_e$ is infinite. Let $t$ be a stage after which all markers \begin{align*} \gamma(0,s),\gamma(1,s),\dots,\gamma(e,s) \end{align*} have stabilized and after which all requirements $R_0,\dots,R_{e-1}$ that ever act have already acted. The protected set \begin{align*} P_e := \{\gamma(0),\gamma(1),\dots,\gamma(e)\} \end{align*} is finite. Since $W_e$ is infinite, choose \begin{align*} x \in W_e \setminus P_e. \end{align*} There is a stage $u \geq t$ such that $x \in W_{e,u}$. If $R_e$ has already acted before stage $u$, then by construction it enumerated an element of $W_e$ into $A$, so $W_e \cap A \neq \varnothing$. If $R_e$ has not acted before stage $u$, then at stage $u$ the element $x$ is not among the protected markers $\gamma(0,u),\dots,\gamma(e,u)$. If $x \notin A_u$, the construction allows $R_e$ to act and enumerate either $x$ itself or a marker equal to $x$ into $A$. If $x \in A_u$, then already $x \in W_e \cap A$. In all cases, \begin{align*} W_e \cap A \neq \varnothing. \end{align*} Therefore every infinite c.e. set intersects $A$, so $\omega \setminus A$ is immune. Since $A$ is c.e. and has infinite immune complement, $A$ is simple. [/step] [step:Reduce $A$ to the halting set] Since $A$ is c.e., membership in $A$ is decidable using an oracle for $K$. On input $x \in \omega$, run the enumeration of $A$ until either $x$ appears or the oracle $K$ confirms that no future computation in the finite search relevant to $x$ will enumerate $x$. Equivalently, use the standard fact that every c.e. set is Turing reducible to the halting set. Hence \begin{align*} A \leq_T K. \end{align*} [/step] [step:Compute the halting set from the final set $A$] We define an oracle procedure $\Phi^A:\omega \to \{0,1\}$ deciding $K$. Given $n \in \omega$, simulate the construction stage by stage. At stage $s \geq n$, query the oracle $A$ on the finitely many current marker values \begin{align*} \gamma(0,s),\gamma(1,s),\dots,\gamma(n,s). \end{align*} Stop at the first stage $s$ for which \begin{align*} \gamma(i,s) \notin A \end{align*} for every $i \in \{0,\dots,n\}$, and output the characteristic value of $K_s$ on $n$. This procedure halts. Indeed, by marker stabilization there is a stage after which each marker $\gamma(i,s)$ for $i \leq n$ has reached its final value $\gamma(i)$, and each final value lies outside $A$. Thus the oracle test eventually succeeds. At the first successful stage $s$, no number $m \leq n$ can enter $K$ after stage $s$. If such an $m$ entered later, the construction would enumerate the current marker tail beginning at $\gamma(m,s)$ into $A$; in particular it would enumerate $\gamma(m,s)$ into $A$. But the oracle test at stage $s$ says $\gamma(m,s) \notin A$, a contradiction. Therefore \begin{align*} K \cap \{0,\dots,n\} = K_s \cap \{0,\dots,n\}. \end{align*} The output of $\Phi^A(n)$ is consequently correct, so $K \leq_T A$. [guided] The reduction $K \leq_T A$ uses the final set $A$ to detect when the first $n+1$ markers have stopped moving. This is exactly why the construction used movable markers rather than a computable permanently reserved complement: the final marker locations are not computable, but they are recognizable with oracle access to $A$. Given $n$, simulate the construction. At a stage $s \geq n$, the finite tuple \begin{align*} (\gamma(0,s),\gamma(1,s),\dots,\gamma(n,s)) \end{align*} is computable from the construction. Ask the oracle $A$ whether any of these finitely many numbers belongs to $A$. If all answers are negative, stop and declare that the current finite approximation $K_s \cap \{0,\dots,n\}$ is already final. Why must this stopping time exist? From the finite-injury argument, each marker $\gamma(i,s)$ with $i \leq n$ has a final value $\gamma(i)$. From the complement argument, each final value satisfies $\gamma(i)\notin A$. Hence, once all these markers have stabilized, the oracle test \begin{align*} \gamma(i,s)\notin A \quad \text{for every } i \leq n \end{align*} will succeed. Why is it safe to stop at the first successful stage? Suppose, toward a contradiction, that some $m \leq n$ enters $K$ after that stage. The construction responds to this entry by enumerating the marker tail \begin{align*} \gamma(m,s),\gamma(m+1,s),\dots \end{align*} as it stands at the relevant stage. In particular, it enumerates the current $m$th marker into $A$. Since the successful oracle test said that this marker was not in the final set $A$, such a later entry cannot occur. Therefore the approximation to $K$ below or equal to $n$ is already correct at the stopping stage. [/guided] [/step] [step:Conclude Turing completeness and simplicity] We have proved that $A$ is c.e., that $\omega \setminus A$ is infinite, and that every infinite c.e. set $W_e$ intersects $A$. Hence $A$ is simple. The reductions established above give \begin{align*} A \leq_T K \end{align*} and \begin{align*} K \leq_T A. \end{align*} Therefore \begin{align*} A \equiv_T K. \end{align*} Thus there exists a simple c.e. set which is Turing complete. [/step]