# Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

In Computability, if we want to prove that a problem is not recursive or not recursively enumerable, we can use e.g. reductions from other non-recursive or non-r.e. problems, Rice's theorem, Rice-Shapiro's theorem, etc. These techniques work thanks to, or are directly based on, the existence of some diagonal argument (i.e. some program $M$ behaves in the opposite way as its input program $M'$, so $M = M'$ is contradictory). In Complexity, if we want to prove that some problem cannot be computed in some time (regardless of any unproved claims such as e.g. $P \neq NP$), we use arguments which are, ultimately, based on some diagonal argument (e.g. the Time Hierarchy theorem proves $EXPTIME$-complete problems are not in $P$, but that theorem is also proved by using a diagonal argument).

So my question is the following. Are all important impossibility results in Computability and Complexity (actual impossibility, not impossibility up to some unproved result) ultimately due to some diagonal argument? That is, does all our important "impossibility knowledge" in Computability and Complexity come from the fact that programs are powerful enough to execute programs?

The only important impossibility result coming to my mind which is not ultimately due to a diagonal argument is that the Ackermann function is not primitive recursive. Am I missing other important counterexamples of this apparent "rule"?

EDIT (Nov 18): Sorry for implying that my question was particularly focusing on the diagonal argument itself, but I'm more interested on all arguments that rely on the self reference of programs (including the diagonal argument, Berry paradox, etc). For simpler languages (e.g. regular or context-free), we have "structural" impossibility arguments based on how these languages are constructed (e.g. pumping lemmas). However, for recursive or r.e. languages, most of impossibility results strongly rely on the self reference of programs. This is what I meant.

• Actually the proof that the Ackerman function is not p.r. is a pretty classic application of the diagonal method! – cody Nov 17 '17 at 16:34
• Also: possible duplicate of cstheory.stackexchange.com/questions/6575/… – cody Nov 17 '17 at 16:45
• Yes, there is a hidden diagonal argument in the proof that a function may not majorize itself, which is referred to here: beta.planetmath.org/SuperexponentiationIsNotElementary – cody Nov 17 '17 at 16:51