Proof of Thm A.4, p. A:42 — for some $r$, $\mathrm{KC}([N_{n,r}])>n+1$ and so $N_{n,r}\in\Pi_Y$

For every $n\in\mathbb N$ there is an $r\in\mathbb N$ such that

and consequently every machine $N$ with $[N]=N_{n,r}$ lies in $\Pi_Y$ (it always halts, and $N_{n,r}(n+1)=1$ with $n+1<\mathrm{KC}([N])$).

In the proof of Theorem A.4 this is the machine that the simulator $S$ cannot distinguish from $Z\in\Pi_N$, although it lies in $\Pi_Y$.

Formalization Note The paper takes $r$ to be a string of Kolmogorov complexity $2n$ and asserts $\mathrm{KC}([N_{n,r}])>n+1$ without proof. The statement here asserts only the existence of a suitable $r$, which is all the proof uses, and does not define the Kolmogorov complexity of strings. The first conjunct rules out the degenerate value $\mathrm{KC}=0$ of a function no machine computes.