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

Improve this question
$\endgroup$
7
  • $\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
    Commented Mar 12, 2017 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
    Commented Mar 12, 2017 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
    Commented Mar 12, 2017 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
    Commented Mar 12, 2017 at 17:52
  • $\begingroup$ @DavidRicherby Some sources use "Gödel numbering" to mean "admissible numbering". $\endgroup$
    – Raphael
    Commented Mar 12, 2017 at 17:54

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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