Questions tagged [diagonalization]
The diagonalization tag has no usage guidance.
14 questions
1
vote
1
answer
32
views
Does an oracle of EXPSPACE-complete $B$ language cause $P^B=EXP^B$
As I have read Sipser's TOC, on page 372, there is a $EXPSPACE$-complete language, say, $B$, i.e. $B\in$ $EXPSPACE$ and every $L\in$ $EXPSPACE$ is polynomial time reducible to $B$.
I also have read ...
- 511
5
votes
2
answers
1k
views
Diagonalisation in the proof of undecidability of the acceptance problem for Turing Machines
It's well-known that the language $A_{TM} = \{\langle M,w\rangle: \text{M is a turing machine that accepts w} \}$ is undecidable.
There's a standard proof that's presented in Sipser's "...
- 151
1
vote
1
answer
48
views
How to separate $TIME(n)$ and $L$?
I'm trying to prove that $TIME(n)\neq L$ by padding technique, yet it has a trouble:
Assume that $TIME(n)= L$, let $A\in TIME(n^2)\backslash TIME(n)$ so $A\notin L$. Let $A_{pad}=\{x01^{|x|^2-|x|-1}|x\...
- 511
1
vote
1
answer
99
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 ...
- 195
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 ...
- 61
3
votes
0
answers
34
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 ...
- 499
1
vote
1
answer
445
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 ...
- 11
1
vote
1
answer
126
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
3
answers
356
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
76
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
331
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 ...
- 8,332
1
vote
1
answer
73
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
1
vote
0
answers
104
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
328
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 ...
- 13