<p>Are there any known diagonalization proofs, of a language not being in some complexity class, which do not explicitly mention simulation?</p>
<p>The standard diagnolization argument goes: here is a list of machines for all languages in a class <span class="math-container">$M...$</span>, here is the list of all arguments <span class="math-container">$w...$</span>, you create an onto map from <span class="math-container">$w$</span>'s to <span class="math-container">$M$</span>'s where a map between a <span class="math-container">$w$</span> and an <span class="math-container">$M$</span> means <span class="math-container">$w$</span> is in the diagonal language <span class="math-container">$L$</span> iff <span class="math-container">$w$</span> is not in <span class="math-container">$M$</span>. Then, an assumption that <span class="math-container">$L$</span> is solved by one of the <span class="math-container">$M$</span>s is not true. However, with this setup, inorder to decide if a particular <span class="math-container">$w$</span> is a member of <span class="math-container">$L$</span>, you need to simulate the corresponding <span class="math-container">$M$</span>.</p>
<p>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.</p>
<p>Can a language be defined, via some <em>&quot;passive&quot;</em> method of diagnolization, that doesn't require simulation of machines that solve the languages in the class you are diagnolizing against?</p>

CC BY-SA 4.0
2020-06-24T17:25:58.993Z
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.
Neal Young
CC BY-SA 4.0
2020-06-24T17:55:37.090Z
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?
Andrej Bauer
CC BY-SA 4.0
2020-06-24T17:58:01.633Z
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."
Andrej Bauer
CC BY-SA 4.0
2020-06-24T18:26:08.693Z
@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.
mark
CC BY-SA 4.0
2020-06-24T18:27:36.343Z
@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.
mark
CC BY-SA 4.0
2020-06-24T19:24:59.260Z
Mark, (i) Your post still mentions *"$w$ is not in $M$"*, which doesn't make sense if $M$ is a class and $w$ is a string.  (ii) The definition of $L$ in my comment does not explicitly mention simulation, and does not require the machines to be simulated in order to be well-defined.  Indeed, simulating a machine on its own encoding to see if it doesn't accept it will not, in general, work (which is, ironically, in some sense the point of that particular diagonalization!).  I guess it's not clear what *"mention simulation"* means.
Neal Young
CC BY-SA 4.0
2020-06-24T19:43:32.323Z
@NealYoung By $M$ I meant a particular machine/ language in the class. I don't mean $w$ doesn't belong to the class. "Mention simulation"  means in order to determine some $w$ a member of $L$, you need to simulate a machine from some class of machines (basically). In your case, in order to determine a $w$ in $L$ you need to run $W(w)$ correct? and if $W(w)=0$ then w is in $L$? And then this language is undecidable because some w will be an encoding of $L$ call it $Wl$ and then $w$ is in $L$ iff $Wl(w) = 0$ which is the contradiction. This is the simulation I'm trying to find a way to avoid.
mark
CC BY-SA 4.0
2020-06-24T19:55:20.530Z
(i) You define $M$ first to be a class of languages, but use it later as something else - a machine whose language is in that class.  Maybe use different notation for: the class, a language in it, and a machine that accepts that language.
(ii) In my comment $L$ is defined for the reader.  For a given $M$, either $M$ accepts $\langle M\rangle$ or it doesn't.  In the latter case, $M$ is in $L$, otherwise it isn't.  For this definition of $L$ be clear to a reader (so as to be used in a diagonalization proof) at no point requires any machine $M$ to be *simulated*.  You must mean something else!
Neal Young
CC BY-SA 4.0
2020-06-24T20:01:03.147Z
Ya, my bad, bad notation. Sorry I must be confused: doesn't $M$ need to be simulated on $M$ to determine if $M$ is in $L$? When you build a solver for your language $L$, I assume that solver will be a universal simulator for all the machines $M$ that you give as input to themselves. then you run $M0(M0), M1(M1)$... and so on. and iff $Mi(Mi)=0$ then $Mi$ is in $L$--the solver goes through and simulates all the $M$'s on themselves?
mark
CC BY-SA 4.0
2020-06-24T20:01:37.437Z
(Continued.) Note that in proofs we often define things that we can't (and don't need to) effectively construct or compute.  Indeed, above I've defined the language $L$ of TM encodings of TM's that don't accept their own input, but that language is not computable.  If it were, would the encoding of the TM that decides it be in $L$ or not? (Either answer gives a contradiction.)  Note that this is a diagonalization proof, and that understanding what $L$ is, and that the argument shows that $L$ cannot be computed, can be done by the reader without even considering simulating any machine.
Neal Young
CC BY-SA 4.0
2020-06-24T20:04:41.163Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/109799/discussion-between-neal-young-and-mark).
Neal Young
CC BY-SA 4.0
2020-06-24T20:07:58.343Z
@NealYoung I think I see your point, that the reader can walk through the logic as to why L is not computable without simulating any machines. To me, your language definition still implies you run machines on their own description in order to compute inputs. I'm wondering if there are any examples of a diagonal argument for a language against some class that doesn't "mention" simulation--ie. doesn't reference machines that need to be run in order to determine its members.
mark
<cc.complexity-theory><turing-machines><enumeration>
Can you diagnolize without mentioning simulation?
mark
# Can you diagnolize without mentioning simulation?

(Asked by: username_0 on 2020-06-24)

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?

**Tags:** cc.complexity-theory, turing-machines, enumeration

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  
> **username_2**: 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."  
> **username_0**: @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.  
> **username_0**: @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.  
> **username_1**: Mark, (i) Your post still mentions *"$w$ is not in $M$"*, which doesn't make sense if $M$ is a class and $w$ is a string.  (ii) The definition of $L$ in my comment does not explicitly mention simulation, and does not require the machines to be simulated in order to be well-defined.  Indeed, simulating a machine on its own encoding to see if it doesn't accept it will not, in general, work (which is, ironically, in some sense the point of that particular diagonalization!).  I guess it's not clear what *"mention simulation"* means.  
> **username_0**: @NealYoung By $M$ I meant a particular machine/ language in the class. I don't mean $w$ doesn't belong to the class. "Mention simulation"  means in order to determine some $w$ a member of $L$, you need to simulate a machine from some class of machines (basically). In your case, in order to determine a $w$ in $L$ you need to run $W(w)$ correct? and if $W(w)=0$ then w is in $L$? And then this language is undecidable because some w will be an encoding of $L$ call it $Wl$ and then $w$ is in $L$ iff $Wl(w) = 0$ which is the contradiction. This is the simulation I'm trying to find a way to avoid.  
> **username_1**: (i) You define $M$ first to be a class of languages, but use it later as something else - a machine whose language is in that class.  Maybe use different notation for: the class, a language in it, and a machine that accepts that language. (ii) In my comment $L$ is defined for the reader.  For a given $M$, either $M$ accepts $\langle M\rangle$ or it doesn't.  In the latter case, $M$ is in $L$, otherwise it isn't.  For this definition of $L$ be clear to a reader (so as to be used in a diagonalization proof) at no point requires any machine $M$ to be *simulated*.  You must mean something else!  
> **username_0**: Ya, my bad, bad notation. Sorry I must be confused: doesn't $M$ need to be simulated on $M$ to determine if $M$ is in $L$? When you build a solver for your language $L$, I assume that solver will be a universal simulator for all the machines $M$ that you give as input to themselves. then you run $M0(M0), M1(M1)$... and so on. and iff $Mi(Mi)=0$ then $Mi$ is in $L$--the solver goes through and simulates all the $M$'s on themselves?  
> **username_1**: (Continued.) Note that in proofs we often define things that we can't (and don't need to) effectively construct or compute.  Indeed, above I've defined the language $L$ of TM encodings of TM's that don't accept their own input, but that language is not computable.  If it were, would the encoding of the TM that decides it be in $L$ or not? (Either answer gives a contradiction.)  Note that this is a diagonalization proof, and that understanding what $L$ is, and that the argument shows that $L$ cannot be computed, can be done by the reader without even considering simulating any machine.  
> **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/109799/discussion-between-neal-young-and-username_0).  
> **username_0**: @NealYoung I think I see your point, that the reader can walk through the logic as to why L is not computable without simulating any machines. To me, your language definition still implies you run machines on their own description in order to compute inputs. I'm wondering if there are any examples of a diagonal argument for a language against some class that doesn't "mention" simulation--ie. doesn't reference machines that need to be run in order to determine its members.  

---

## 0 answers

