Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [diagonalization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
82 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 ...
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 ...
1 vote
2 answers
298 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 ...
3 votes
0 answers
31 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
386 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
103 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 $...
0 votes
3 answers
335 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{ ...
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 ...
2 votes
1 answer
289 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 ...
1 vote
1 answer
63 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 ...
1 vote
0 answers
92 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 ...