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

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 ...
D.W.'s user avatar
  • 161k
10 votes

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 ...
John L.'s user avatar
  • 39k
5 votes

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: ...
Andrej Bauer's user avatar
  • 30.8k
4 votes

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)$.
Yuval Filmus's user avatar
4 votes

Proving FPT is strictly contained in XP

By the time hierarchy theorem, there is a family of languages $(L_k)_{k \in \mathbb{N}}$ such that $L_k$ is decidable in time $O(n^{2^{k+1}})$, but not in time $O(n^{2^k})$. We define $\mathcal{L} = \{...
Arno's user avatar
  • 3,113
3 votes

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

TLDR: It means that they are using a technique to represent Turing machines as numbers in order for the circularity to be possible, hence "arithmetization". It is not trivial (especially, it ...
Sam Gutkind's user avatar
3 votes

Can the diagonal language be empty?

Since the diagonal language is not computable but the empty language is computable, that means that those languages are different.
Nathaniel's user avatar
  • 15.7k
3 votes

Hilbert's Hotel for guests with infinite string name

An infinite string is uniquely identified by a function $s:\mathbb{N}\rightarrow \{A,B\}$, such that $s(n)$ is the $n$'th character in the string. The number of such functions is known to be: $|\{A,B\}...
nir shahar's user avatar
  • 11.6k
2 votes

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 ...
chi's user avatar
  • 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 ...
emesupap's user avatar
  • 183
1 vote

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 ...
idmean's user avatar
  • 746

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