What is the relation between recursive languages and partial recursive functions?

Question

From Introduction to Automata Theory, Language, and Computation by Ullman et. al.:

The Turing machine is studied both for the class of languages it define (called the recursively enumerable sets) and the class of integer functions it computes (called the partial recursive functions).

1. What is the relation between recursive enumerable languages and partial recursive functions? (notice "recursive" in both terms, and "partial" in "partial recursive functions" are also often omitted)

   Is it correct that the membership decision problem of a r.e. language is a partial recursive function, so can be computed by a TM?

2. What is the relation between recursive languages and total recursive functions? (The similarity in the two terms has led me to a lot of confusions and mix-ups.)

Thanks.

Answer 1

1. Strictly speaking the two are simply different things. The "membership decision problem of a r.e. language" cannot be an integer function, because it does not take an integer as input. But with some coding we can connect the two. For example, we can interpret the input word over an n-ary alphabet as a number in base n+1 (exclude the zero for uniqueness of representation). Then we can look at the membership as an integer function, and indeed just the ones for r.e. sets are partial recursive.

The other way around, funtions have both input and output, while language deciders take a word and end in a certain class of state (or loop forever). So if we want to consider what functions they can compute we usually look at the sets of ordered pairs $$\{(x,f(x)): x \text{ in the domain} \}.$$ And again one can show that just the partial recursive functions result in r.e. sets.

2. The answer is just as above. They are different things, but deep down they are the same.

Answer 2

(Below, for simplicity all functions are unary. Also, "$\uparrow$" denotes "is undefined." Finally, for simplicity I'll think of languages as sets of natural numbers as opposed to sets of strings, although this is purely superficial.)

---

The key is the following "translation" from partial functions to sets:

Given a partial function $f$, let $$Graph_f=\{\langle a,b\rangle: f(a)=b\}$$ (where "$\langle\cdot,\cdot\rangle$" is your favorite pairing operation).

Note that $Graph_f$ is defined for all partial functions $f$, not just the recursive ones. The construction $f\mapsto Graph_f$ lets us translate properties of functions to corresponding properties of sets, and in general all computability-theoretic properties will "match up" appropriately. In particular, we have:

Suppose $f$ is a partial function. Then the following are equivalent: $(i)$ $f$ is a partial recursive function. $(ii)$ $Graph_f$ is recursively enumerable.

(Indeed, this is one way that partial recursive functions are sometimes defined in the first place. Moreover, note that in much of logic a function literally is its graph, so it's unsurprising to see this sort of correspondence.)

---

On a less-immediate note, observe that the further assumption of totality simplifies things substantially:

Suppose $f$ is a total function. Then the following are equivalent: $(i)$ $f$ is recursive. $(ii)$ $Graph_f$ is r.e. $(iii)$ $Graph_f$ is recursive.

Clearly $(iii)\rightarrow (ii)$, and $(ii)\rightarrow (i)$ by the previous observation. To see $(i)\rightarrow (iii)$, suppose $f$ is total recursive and we want to check whether $\langle a,b\rangle\in Graph_f$; we simply run (the computation of) $f$ on input $a$ until it halts and outputs some $n$, which it must since $f$ is total, and then we check whether $n=b$.

If we drop the totality assumption this breaks down: the function $$h_X(n)=\begin{cases} n & \mbox{ if $n\in X$}\\ \uparrow & \mbox{ otherwise}\\ \end{cases}$$ is partial recursive whenever $X$ is r.e., but $Graph_{h_X}=\{\langle x,x\rangle: x\in X\}$ has the same Turing degree as $X$, so if $X$ is a non-recursive r.e. set then $h_X$ is a partial recursive function with r.e. but non-recursive graph.

---

It's also worth noting that there's also a translation "dual" to the $f\mapsto Graph_f$-construction, although it's a bit more finicky. Every r.e. set $X$ has a "one-at-a-time" enumerator - that is, a machine $M$ such that for each $s$ there is at most one $t_s$ such that $M$ accepts $t_s$ in exactly $s$ steps. The associated map $$g_M(s)=\begin{cases} t_s & \mbox{ if $M$ accepts some string in exactly $s$ steps}\\ \uparrow & \mbox{ otherwise} \end{cases}$$ is partial recursive and we have $Graph_{g_M}=X.$

The reason this is more finicky is that $M$ is not uniquely determined by $X$ - every r.e. $X$ will have many such $M$s.