Share Your Experience: Take the 2024 Developer Survey

# Tag Info

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

I would guess/assume that by "arithmetization", they mean the concept that every Turing machine can be associated with a bit-string or natural number (the fact that we can encode a ...
• 161k
Accepted

### Can the diagonal language be empty?

Here is a simple direct proof that $L_{\text{diag}}$ is not empty. Let $N$ be a Turing machine that does not accept any word. For example, a Turing machine that just loops forever. Suppose $N$ is ...
• 39k
Accepted

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

Unless you found an unusual proof, they're all refutations by contradiction (not "proofs by contradiction", although that is common parlance) and they all are qlso a form of diagonalization: ...
• 30.8k
Accepted

### Can you diagonalize a language out of CSL?

This is accomplished by the nondeterministic space hierarchy theory, given that CSL is the same as $\mathsf{NSPACE}(n)$.
• 277k
Accepted

• 11.6k

### Can the diagonal language be empty?

Others have already suggested the simplest and most elegant ways to prove that the diagonal language is not empty. Indeed, we can proceed by contradiction, and argue that if the diagonal language were ...
• 14.6k
1 vote

### Prove Language Is Undeciable Using Diagonalization

Your proof is roughly correct, indeed showing that |Power(L)| is uncountably infinite is usually done via diagonalization. Here, L is the set of strings over the unary alphabet, and a language is any ...
• 183
1 vote
Accepted

### M does not accept [M] | 'Correction' of proof possible?

Even with your restriction $D$ is undecidable. You can still reduce the halting problem of a TM $A$ on a word $x$ to $D$. Construct a TM $B$ that simulates $A$ on $x$. If $A$ halts, $B$ accepts its ...
• 746

Only top scored, non community-wiki answers of a minimum length are eligible