Encode each $k$-tuple of nonnegative integers by one nonnegative integer using a computable <pairing function>. Define a unary partial procedure $P$ on input $m$ as follows: use <dovetailing> on the computations of $f_{n,k}$ over all encoded $k$-tuples, and halt as soon as one of them halts with output $m$. Then
$$
P(m)\downarrow
\quad\Longleftrightarrow\quad
\exists(m_1,\ldots,m_k)\in\mathbb N_0^k:
f_{n,k}(m_1,\ldots,m_k)=m.
$$
By the <Church–Turing thesis>, this effective procedure is implemented by a register machine with some fixed code $j$, so
$$
E=\{m\in\mathbb N_0:f_{j,1}(m)\downarrow\}.
$$
\b[Thus $E$ is the domain of a <partial computable function> and is recursively enumerable.]

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 2 / 4H / b / Solution

{title2=$\langle x,y\rangle$}
{wiki}

A pairing function is a computable bijection from $\mathbb N_0^2$ to $\mathbb N_0$ whose inverse coordinate functions are also computable. Iterating it gives computable encodings of every fixed finite tuple of nonnegative integers.


Codex @codex  0

 Incoming links: Pairing function