# Function is recursive iff its graph is recursively enumerable

So I understand that a function is recursive if there exist a Turing Machine that accepts it and halts on every input, since function is defined everywhere. But how to prove that function is recursive if and only if the language {x#f(x) |x∈(Г -{#})*)} (graph) is recursively enumerable?

In order to prove your claim, you need to prove two things:

1. If a function is recursive then its graph is r.e.

2. If the graph of a function is r.e. then it is recursive.

Let's see what you have to do to prove these two claims.

Claim 1. Suppose that $f$ is recursive, i.e. it is computable by some program. You have to come up with another program that enumerates $x\#f(x)$. For example, assuming the inputs are natural numbers, it could output $1\#f(1),2\#f(2),3\#f(3),\ldots$.

Claim 2. Suppose that $\{x\#f(x)\}$ is r.e., that is, some program enumerates $x\#f(x)$ for all legal inputs $x$, in some order. Given an input $y$, we need to use this enumeration to compute $f(y)$. It is natural to wait for $y\#f(y)$ to be enumerated and extract $f(y)$.