1
$\begingroup$

This might be a slightly strange or irrelevant question. My apologies if it is. I'll try to formulate it the best I can.

First, here is an hypothesis: diagonalization is syatematically used to prove that a set is a proper subset of another set by constructing an object that exists in the latter but not in the former.

Following Peter Smith in An Introduction to Gödel's Theorems, let's call this "diagonalizing out". And, please, feel free to object to this first hypothesis if needed be.

In recursion theory, we diagonalize out at a "sub-computable level". By this, I mean that the diagonalization is used to separate two classes that are both computable, i.e. the p.r. functions and the \mu-recursive functions. On the contrary, with Turing machines, we systematically diagonalize out at a "supra-computable level", whether it is to show that there are languages that are not Turing-recognizable (using Cantor's diagonalization) or to show that there are Turing-recognizable languages that are not decidable (e.g. halting problem). I don't recall ever seeing any diagonalization having to do with two computable classes of languages.

This asymmetry surprises me. Do you have an explanation for it? Can we find the equivalent of the non p.r. diagonal function with TM theory, maybe using Linear Bounded Automata?

Thank you in advance for your insights!

Improve this question
$\endgroup$
6
  • $\begingroup$ Are you familiar with the time hierarchy theorem and space hierarchy theorem? $\endgroup$
    – Yuval Filmus
    Commented Jun 21, 2021 at 19:16
  • $\begingroup$ I'm only familiar with the usual space and time complexity theory - not much more than that. I saw somewhere that you mentioned p.r. functions being somewhere between LBAs and mu-recursive functions because of LBA's space bounds (BTW, I thought that was really interesting) - does it have something to do with that? But I'm surprise that it would involve complexity while diagonalisation is really about the outer limit of computability rather than the inner hierarchy (awkwardly said, sorry). $\endgroup$
    – Hugolin Bergier
    Commented Jun 21, 2021 at 19:31
  • $\begingroup$ They are the standard application of diagonalization in complexity theory. $\endgroup$
    – Yuval Filmus
    Commented Jun 21, 2021 at 19:32
  • $\begingroup$ Ok, thank you! I'll look those up. Indeed, those are use of the diagonalization within the classes of computable functions. That's what I was looking for. $\endgroup$
    – Hugolin Bergier
    Commented Jun 21, 2021 at 19:42
  • $\begingroup$ Would you say that there is a link between the diagonalisation to build a non p.r. function and the time hierarchy theorem? $\endgroup$
    – Hugolin Bergier
    Commented Jun 22, 2021 at 8:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.