1
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ Try first constructing such a numbering in which $I = \mathbb{N}$, and use this numbering to solve your question. Give it a few hours. $\endgroup$ – Yuval Filmus Mar 12 '17 at 16:14
  • $\begingroup$ 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. $\endgroup$ – David Richerby Mar 12 '17 at 16:27
  • $\begingroup$ 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)$) $\endgroup$ – puhsu Mar 12 '17 at 16:35
  • $\begingroup$ 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? $\endgroup$ – Raphael Mar 12 '17 at 17:52
  • $\begingroup$ @DavidRicherby Some sources use "Gödel numbering" to mean "admissible numbering". $\endgroup$ – Raphael Mar 12 '17 at 17:54
0
$\begingroup$

Hint:

  • There are countably many computable functions defined at zero, and countably many computable functions undefined at zero.
  • There are countably many natural numbers divisible by 2, and countably many natural numbers not divisible by 2.

Put the two facts together.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.