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.
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 ...
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$....
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 $...
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 ...
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 ...
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_{...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
undecidability × 821turing-machines × 424
computability × 391
reductions × 124
halting-problem × 120
formal-languages × 101
semi-decidability × 86
decision-problem × 55
complexity-theory × 47
automata × 38
context-free × 37
proof-techniques × 37
rice-theorem × 35
regular-languages × 21
finite-automata × 18
formal-grammars × 18
logic × 17
reference-request × 12
computation-models × 12
closure-properties × 12
decidability × 11
algorithms × 9
terminology × 9
first-order-logic × 9
pushdown-automata × 8