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.
- 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 ...
- 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$....
- 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 $...
- 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 ...
- 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 ...
- 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_{...
- 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 ...
- 738
Only top scored, non community-wiki answers of a minimum length are eligible