Questions tagged [diagonalization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6 votes
2 answers
2k views

What does it mean to prove the halting problem is undecidable "using arithmetization"?

In version gamma of the ACM/IEEE/AAAI Computer Science Curricula 2023, on page 50, one of the illustrative learning outcomes for the "Computational Models and Formal Languages" section of ...
user164282's user avatar
4 votes
1 answer
74 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 ...
Hugolin Bergier's user avatar
3 votes
0 answers
30 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 ...
441Juggler's user avatar
2 votes
1 answer
280 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 ...
Discrete lizard's user avatar
  • 8,248
1 vote
1 answer
77 views

What is the role of diagonalization in the proof of undecidability of the halting problem?

I'm trying to understand the proof of undecidability of the halting problem. Some resources give a short proof based on a proof by contradiction. There is no mention of diagonalization. But some ...
Sanyo Mn's user avatar
  • 195
1 vote
2 answers
291 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 ...
Dev_anon101's user avatar
1 vote
1 answer
376 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 ...
EdisonCanaj's user avatar
1 vote
1 answer
62 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 ...
David's user avatar
  • 25
1 vote
1 answer
100 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 $...
Konschi's user avatar
  • 13
1 vote
0 answers
87 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 ...
Hugolin Bergier's user avatar
0 votes
3 answers
330 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{ ...
Max's user avatar
  • 111