Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [diagonalization]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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
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 ...
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
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