Questions tagged [diagonalization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers
17 views

Understanding a black-box vs white-box simulation and relativization

I am trying to understand the relativization barrier from Baker Gill Solovay (BGS). About this barrier, I have heard that it only applies when using a black-box simulation. Hence, my question is, what ...
1 vote
1 answer
57 views

Prove Language Is Undeciable Using Diagonalization

I was given the following problem and told it has to be solved using diagonalization. However, I am confused as to why diagonalization would be the solution. Would the answer not be since L is ...
1 vote
1 answer
44 views

Why is the language containing the Turing machines which only accept their own encoding not applicable to the diagonalization proof?

I saw this question and asked myself why the original problem is not solvable through diagonalization. Let $$L = \bigl\{\langle M \rangle \mid L(M) = \{\langle M\rangle\}\bigr\}$$ Take the complement $...
  • 13
0 votes
0 answers
29 views

How to show that the set of all turing machines that halt on a blank tape form a recursively enumerable set

I learned in my class that set of all Turing machines that halt on a blank tape form a recursively enumerable set. I was told that you can prove it using an argument similar to the diagonalization ...
0 votes
3 answers
264 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{ ...
  • 111
4 votes
1 answer
68 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 ...
2 votes
1 answer
180 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 ...
  • 7,008
1 vote
1 answer
40 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 ...
  • 25
0 votes
0 answers
44 views

The role of diagonalization - asymmetry between TM and Recursion Theory

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 ...
1 vote
2 answers
208 views

Hilbert's Hotel for guests with infinite string name

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 ...