Function is recursive iff its graph is recursively enumerable

Question

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?

Answer 1

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)$.

Your task now is to flesh out these proof sketches.

Answer 2

Unfortunately, there is a painful terminological overloading of the term "recursive" in computability theory. So you must pay attention if you are talking about a function or a set.

In relation to functions, "recursive" is used as a synonym of "computable". This is also the intended meaning of the world in the definition of "recursively enumerable set", since the attribute "recursive" refers to the enumeration function, that must be computable, and not to the set being enumerated.

In relation to sets, "recursive" means decidable. This is due to the fact that you are implicitly referring to the "recursiveness" (that is, computability) of the characteristic function of the set, that by definition is a total function.

So, coming to your question, the fact that the function is recursive only means that it is computable, but does not imply that it is also total.

For total functions, the function is recursive if and only if its graph is recursive, that is probably what was puzzling you.