# Questions tagged [diagonalization]

The tag has no usage guidance.

6 questions
Filter by
Sorted by
Tagged with
225 views

### Can the diagonal language be empty?

We defined the diagonal language as follows in the lecture: \begin{align*} L_{\text{diag}}=\left\{w \in \left\{0, 1\right\} ^{*}\mid w=w_{i} \text{ for some }i \in \mathbb{N} \text{ and }M_{i} \text{ ...
64 views

### Can you diagonalize a language out of CSL?

In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we ...
141 views

### Proving FPT is strictly contained in XP

In their book Fundamentals of Parameterized Complexity, Downey and Fellows claim (in chapter 27.1) that $\mathrm{FPT}\subsetneq \mathrm{XP}$, and that this is a "basic result" that follows ...
30 views

### M does not accept [M] | 'Correction' of proof possible?

The language $D=\{[M]|M([M])=0\}$ is not decidable because of the following argument: Suppose there was a $TM \space M_D$ that decides $D$. Then if we gave $M_D \space [M]$, there would be two ...
I was watching this video How An Infinite Hotel Ran Out Of Room, by Veritasium. The video says that it is not possible to fit names made of infinite strings of $\{A,B\}$. We know we can fit infinite ...