# Graphs of recursive functions

Recently I've been studying the relationship between recursiveness of a function and recursiveness of its graph (i.e. recursiveness of the characteristic function of the graph). First, we have

Theorem 1: If $$f:\mathbb{N}\to\mathbb{N}$$ is primitive recursive, then its graph is primitive recursive.

The converse is false, as witnessed by the Ackermann function for example. In an excellent answer about this, it was noted that this failure can be understood in terms of the distinction between computation and verification -- informally, computation is generally "harder" than verification, so just because we can verify whether $$f(x)=y$$ primitive recursively doesn't mean we can compute $$f(x)$$ primitive recursively.

When we switch from primitive recursiveness to total recursiveness, we have

Theorem 2: If $$f:\mathbb{N}\to\mathbb{N}$$ is total, then $$f$$ is (total) recursive if and only if its graph is recursive.

So with total functions, if recursiveness is our only measure of "complexity", then it seems computation and verification are equally "hard". For partial recursvieness we have:

Theorem 3: If $$f:\mathbb{N}\to\mathbb{N}$$ is partial, then $$f$$ is (partial) recursive if and only if its graph is recursively enumerable.

Notably if $$f$$ is partial recursive, its graph need not be recursive. So with partial functions, it seems things have gotten flipped, and verification is now "harder" than computation.

I'm looking for an intuitive way to understand the relationship between these theorems, especially as it pertains to the analogy mentioned. My current feeling is that in the case of Theorem 2, it's not surprising just because we're talking about computability in both cases. And in the case of Theorem 3, it's misleading because characteristic functions are always total -- that is, the verification must be total verification. For comparison it might be better to consider

Theorem 4: If $$f:\mathbb{N}\to\mathbb{N}$$ is partial, then $$f$$ is (partial) recursive if and only if the "partial characteristic function" $$\chi_f$$ of its graph is (partial) recursive, where $$\chi_f(x,y)=\begin{cases}1&\text{if }f(x)\downarrow=y\\ \uparrow&\text{otherwise} \end{cases}$$

Any thoughts are welcome. But please note I'm not seeking proofs or proof explanations for the above theorems.

• I feel like Theorem 3 doesn't really say that verification is harder than computation. If all you know is that $f$ is partial computable, this makes your life quite hard if you want to compute $f$, since for any given input, if the program to compute $f$ hasn't halted after a while, you have no way of knowing if that's because $f$ is undefined or because it just has to run a bit longer. Commented May 18 at 10:40

The theorem 1 is misleading, because verification will take almost the same time than computation. Difference is that complexity is based on input size. As output is very large, computation has a terrible complexity, but verification seems to be easy, however for the same input, computing $$f(x)=y$$ from $$x$$ or verifying $$f(x)=y$$ will take almost the same time.
Intuitively, it comes from the fact that, in the general case, the only thing we can do to verify $$f(x)=y$$ is to compute $$f$$. And it comes from the fact that, in the general case, we can't extract any property from a program (this is related to the Rice theorem) that would help us verify the result faster than compute it.