4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 18 at 10:40

1 Answer 1

1
$\begingroup$

What I intuitively understand today is that, for finite computations*, computation and verification are always almost the same difficulty (as long as your difficulty class is stable by exponential transformation, which is clearly the case for primitive computable).

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.

Same thing for theorem 3. When you compute f, you don't know if you'll get a result. Well, verifying will lead to the same problem. Partially recursive and recursive enumerability are almost the same, so here again, computing and verifying share the same "complexity".

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.

Note: * I underline "finite computations", which is the classical model of computation because it's false for more general models, like Turing machines computing on infinite countable ordinal times, where some values can be non infinite-computable but can be infinite-verifiable

$\endgroup$
1
  • $\begingroup$ +1: the point about Theorem 1 is that the counter-example involving the Ackermann function exploits specific properties of that function which mean that its graph is easier to decide than the function is to compute. This doesn't say anything general about the relative difficulty of the decision problem for the graph (verification) and computation of the function. $\endgroup$
    – Rob Arthan
    Commented May 22 at 21:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .