6 votes
Accepted

If $A ⊆ B ⊆ C$ and $A$, $C$ are decidable, then $B$ is decidable

There exists undecidable languages. $A = \emptyset$ and $C = \Sigma^*$ are decidable. ???? Profit.
user avatar
  • 7,127
4 votes

Undecidability in optimal data compression

The length of the shortest program to produce a given string is known as the Kolmogorov complexity of that given string. (Of course, some details are needed to give a formal definition, but this is ...
user avatar
  • 306
3 votes

Why is $A_{TM}$ not mapping reducible to $E_{TM}$?

Given $\langle M,w\rangle\in A_{TM}$, the mapping $f$ in the question maps $\langle M,w\rangle$ to $\langle M_1\rangle$, where Turing machine $M_1$ accepts input $x$ iff $x$ is $w$ and $M$ accepts $w$....
user avatar
  • 33k
3 votes
Accepted

Proving Undecidability of this Language

Fix $i$ and $j$ as two positive integers, as per your comment. Consider the language $H$ containing all pairs $\langle T, y\rangle$ where $T$ is (encoding of) a Turing machine, $y \in \Sigma^*$, and $...
user avatar
  • 22.7k
3 votes
Accepted

Disprove: if L is decidable then Prefix(L) is decidable

It is correct that if $L$ is decidable language $\text{Prefix}(L)$ can be undecidable. The language $L$ given in the question is a concise example of a decidable language the prefix language of which ...
user avatar
  • 33k
2 votes
Accepted

If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?

There is no definitive answer. If predicate $P$ is partially-decidable, $\neg P$ can be decidable, partially-decidable or undecidable. Let $P(n)$ be "is $n>1$?". $P$ is partially ...
user avatar
  • 33k
1 vote

Why is $A_{TM}$ not mapping reducible to $E_{TM}$?

Note: This answer was given before the definition of $A_{TM}$ was added to the question and was assuming the following definition instead $A_{TM} = \{ \langle T \rangle \mid L(T) = \Sigma^* \}$. $E_{...
user avatar
  • 22.7k
1 vote
Accepted

Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?

It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate to prove that an arbitrary TM will run forever. If $L$ is not ...
user avatar

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