Let $f_{n, k}$ be the partial function on $k$ variables that is computed by the $n$th machine (or the empty function if $n$ does not encode a machine).

Define the halting set $\mathbb{K}$.

Given $A, B \subseteq \mathbb{N}$, what is a many-one reduction $A \leqslant_{m} B$ of $A$ to $B$ ?

State the $s-m-n$ theorem and use it to show that a subset $X$ of $\mathbb{N}$ is recursively enumerable if and only if $X \leqslant_{m} \mathbb{K}$.

Give an example of a set $S \subseteq \mathbb{N}$ with $\mathbb{K} \leqslant_{m} S$ but $\mathbb{K} \neq S$.

[You may assume that $\mathbb{K}$ is recursively enumerable and that $0 \notin \mathbb{K}$.]