# Numbering of computable functions

Is there a numbering (not Gödel numbering) of all computable functions $U(p, x)$, such that the set of numbers of functions defined in zero is exactly the set of even numbers. More formally: $I = \{p,\ |\ U(p, 0)\ \mathrm{defined}\} = 2\mathbb{N}$.

My guess that it's true. But I'm not sure how to prove it.

## Ideas:

We can construct a numbering of all computable functions, defined in zero using the function $F(p, x, t)$ which is equal to $0$ if $U(p, x)$ hasn't finished work in $t$ steps and $1$ in other case. We can do it because set of pairs $(p, t)$ is enumerable.

Then, having this function $V(p, x)$ and some other numbering $U(p, x)$ we can construct numbering

$$U'(p, x) = \begin{cases} V(\frac{p}{2}, x)\ \ if\ p \vdots 2\\ U(\frac{p + 1}{2}, x)\ \ if\ p \not\vdots 2 \end{cases}$$

• Try first constructing such a numbering in which $I = \mathbb{N}$, and use this numbering to solve your question. Give it a few hours. Commented Mar 12, 2017 at 16:14
• What do you mean by "not Gödel numbering"? Any bijection between computable functions and the natural numbers is a Gödel numbering: that's what the term means. Commented Mar 12, 2017 at 16:27
• I meant that this numbering is not the main numbering. (By main numbering i mean such a numbering $U(k, x)$ that for any computable function $V(p, x)$ there exist function $s(p)$ such that $U(s(p), x) = V(p, x)$) Commented Mar 12, 2017 at 16:35
• Welcome to Computer Science! You can show such a claim by giving the numbering. What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? Commented Mar 12, 2017 at 17:52
• @DavidRicherby Some sources use "Gödel numbering" to mean "admissible numbering". Commented Mar 12, 2017 at 17:54