= Solution
A <recursive function> $f:\mathbb N^k\to\mathbb N$ is a <total computable function>: an algorithm halts on every input and returns the specified value. Equivalently it is an everywhere-defined member of the <partial recursive functions>, obtained from the initial zero, successor and projection functions by composition, <primitive recursion> and <unbounded minimization>. In minimization $\mu y\,[g(\mathbf x,y)=0]$, the sequential search must find a zero after all earlier tests have been defined; otherwise the result is undefined. The <Church–Turing thesis> allows the algorithmic formulation here.
A <recursively enumerable set> $E\subseteq\mathbb N^k$ is the domain of a <partial computable function>. Thus an algorithm halts and accepts exactly on members of $E$, and may run forever on nonmembers. Equivalently an algorithm lists exactly its elements, allowing repetition and allowing an empty output for the empty set. To pass from a listing to a membership semidecision, wait for the input to appear. To pass back, use <dovetailing> on all inputs and list each whose recognizing computation halts. This differs from a <recursive set>, whose zero-one characteristic function is total recursive and decides both membership and nonmembership.
Back to article page
