I have known that:

A function $\Bbb N → \Bbb N$ is recursive if and only if its graph is a recursive subset of $\Bbb N^2$.

Now I am considering about the partial functions. Is it the fact that:

A partial function $f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive if and only if its graph is a recursively enumerable subset of $\Bbb N^2$.

If it is true (or one direction is true), may I please ask for a proof? Or some reference would be also appreciate (I searched it but did not obtain any useful result).

Note: It is from a math course (and I have asked in the math site). And I have not learnt about the related things about computer science (for instance, I have not learnt about the Turing machine and I have no skill of coding). So sorry I cannot understand explanations which involves the usage of terms in computer science. May I please ask for a mathematical approch please? Thanks!

I have done some search but I cannot find some helpful material. Any reference would be appreciate to. Thanks a lot.


closed as unclear what you're asking by Yuval Filmus, David Richerby, Rick Decker, Evil, Juho May 25 '17 at 16:57

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Unfortunately, we cannot answer questions on computability without using computability. $\endgroup$ – Yuval Filmus May 16 '17 at 7:23
  • $\begingroup$ Theoretical computer science is mathematics. Computability has to be with respect to some model of computation: if you're not using Turing machines, that's fine, but what are you using? $\endgroup$ – David Richerby May 16 '17 at 10:15
  • $\begingroup$ @DavidRicherby It is just a topic of a logic course, I think maybe latter we will see something related to that, but so far I have not learnt about it. $\endgroup$ – PropositionX May 16 '17 at 10:18
  • $\begingroup$ @PropositionX OK, fine. But what definition of computability are you working with? If you don't have a definition, you can't prove anything. $\endgroup$ – David Richerby May 16 '17 at 13:30
  • $\begingroup$ @DavidRicherby This section is called computability but the word seems not appear in the whole section in my text... And later we will use algorithmic instead of the term computability(which according the book is the same as "computable"). But now here we just told to prove things according to mathematical definition. So it seems to be we are not allowed use some tools of computer science. $\endgroup$ – PropositionX May 16 '17 at 13:37

A $k$-ary relation $R \subseteq \mathbb{N}^k$ is recursively enumerable if its indicator function $f_R$ defined by

$$f_R(n_1,\ldots,n_k) = \begin{cases} 1 & \text{if } R(n_1,\ldots,n_k) \\ 0 & \text{otherwise} \end{cases}$$

is a partial recursive function.

So if $f: \mathbb{N} \rightarrow \mathbb{N}$ is a partial recursive function, it is easy to see that the graph

$$R_f = \{ (m,n) \mid f(m) = n \}$$

is a recursively enumerable set. We have $f_{R_f}(m,n) = 1 - \mathrm{sg}(f(m) - n)$, where $\mathrm{sg}(n)$ is the primitive recursive function that is $0$ for $n=0$ and $1$ otherwise. Since we can express the indicator function $I_{R_f}$ of the graph as the composition of partial recursive functions, we therefore conclude that it is also a partical recursive function.

Conversely, if $$R_f = \{ (m,n) \mid f(m) = n \}$$

is a recursively enumerable set with indicator function $I_{R_f}$, then

$$f(m) = \mu n. [ (1 - I_{R_f}(m,n)) = 0 ] $$

Here $\mu n.P(n)$ denotes unbounded mineralization over the unary predicate $P(n)$.

  • $\begingroup$ To confirm, for the partial recurs $\implies$ graph recursive enumerable direction, may I please ask if you use this version of definition that "the characteristic function is a partial recursive function" to conclude that the set is recursive, and thus recursively enumerable? $\endgroup$ – PropositionX May 16 '17 at 9:52
  • $\begingroup$ I did not. None of the binary relations here are known to be recursive. We can express the characteristic function $I_{R_f}$ of the graph as the composition of partial recursive functions, and we therefore conclude that it is also a partical recursive function. $\endgroup$ – Hans Hüttel May 16 '17 at 10:03

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