0
$\begingroup$

Are there any known diagonalization proofs, of a language not being in some complexity class, which do not explicitly mention simulation?

The standard diagnolization argument goes: here is a list of machines for all languages in a class $M...$, here is the list of all arguments $w...$, you create an onto map from $w$'s to $M$'s where a map between a $w$ and an $M$ means $w$ is in the diagonal language $L$ iff $w$ is not in $M$. Then, an assumption that $L$ is solved by one of the $M$s is not true. However, with this setup, inorder to decide if a particular $w$ is a member of $L$, you need to simulate the corresponding $M$.

Even with indirect diagnolization: (essentially) you assume two complexity classes are equal, you prove more and more equalities until you show two classes equal that you can separate via the ^ same ^ type of diagnolization. Although you are not simulating machines in the original class you want to separate, you are still relying on the construction of a language that requires simulation (of machines for languages in the class it is a diagonal of) to determine its members.

Can a language be defined, via some "passive" method of diagnolization, that doesn't require simulation of machines that solve the languages in the class you are diagnolizing against?

$\endgroup$
  • 2
    $\begingroup$ The wording seems unclear in a couple of ways. First, you have in mind restricting to some class of diagonalization arguments (e.g., not the one showing the reals are uncountable), but it's not clear exactly what that class is. (E.g., we can certainly define a language $$L=\{\langle M\rangle : \text{ TM } M \text{ does not accept its own encoding}\}$$. This definition can be viewed as a diagonalization but does not involve any simulation at all.) Also, in the second paragraph, you say that $M$ is a class of languages, but then "iff $w$ is not in $M$, $M(w)=0$", doesn't make sense. $\endgroup$ – Neal Young Jun 24 at 17:25
  • 2
    $\begingroup$ The question is unclear. What does it mean for a construction to "require" simulation? In fact, how do you define "the proof uses simulation"? Without such a definition, the best you can ask is "are there any known diagonalization proofs which do not explicitly mention simulation". Is that what you are asking? $\endgroup$ – Andrej Bauer Jun 24 at 17:55
  • 2
    $\begingroup$ To illustrate why your question is unclear, here is the sort of answer that you will dislike but is formally correct: "Sure, instead of simulating machines just compile them." $\endgroup$ – Andrej Bauer Jun 24 at 17:58
  • 1
    $\begingroup$ @NealYoung the M(w)=0 was just an exposition of the comment before it, removed it it. In your example, in order to determine if w is a member of L I still technically need to run the machines. its a diagnolization because we get a contradiction when you do that, but membership is still dependent on a machine M being run on its own encoding. I'm trying not to restrict the class of diagonal arguments--just asking abstractly: "are there any known diagonalization proofs (of a language not being in some complexity class) which do not explicitly mention simulation" as Andrej says. $\endgroup$ – mark Jun 24 at 18:26
  • 1
    $\begingroup$ @AndrejBauer ya... my question is hard for me to formalize. ill work on it. But for now let's go with your version of the question restated in the comment above. $\endgroup$ – mark Jun 24 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.