# Questions tagged [undecidability]

Questions about problems which cannot be solved by any Turing machine.

713 questions
Filter by
Sorted by
Tagged with
198 views

### Decidability of $E_{TM}$ and $A_{TM}$ for “erasing” Turing machines

Why is the $A_{ETM}$ for a variant of a Turing machine (an erasing Turing machine), where changing a tape symbol to a nonblank symbol is prohibited, decidable? Why does the following diagonalization ...
638 views

### Decidability of equivalence of two context free grammars

I got a question regarding the decidability of equivalence of two context free grammars: Construct a Turing machine that decides whether $L(G) = L(H)$, where $G$ and $H$ are two context free ...
83 views

I am a bit confused on how to reduce a problem. I'll give an example: Let's say there is a problem called HALTEMPTY and we know it is undecidable. $HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ... 1answer 42 views ### Problems with decidability open (for a long time) proven decidable It seems to me that problems whose dedicability remains open for a long time, if resolved, tend to end up being undecidable. A prominent example would be (e.g.) Hilbert's tenth problem, whose ... 1answer 121 views ### Is {<M,w>|M prints more than 300 non-blanks on input w} decidable? Let $$L_{300}=\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\}.$$ Is$L_{300}$decidable? My intuition is it is decidable because given$M$and$w$, we need ... 1answer 283 views ### Prove that it is undecidable whether a given LBA accepts a regular set I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than ... 1answer 84 views ### Solving problems that DTM can't solve Let L be a problem that DTM can't solve. Can we prove that there is an abstract machine that can solve this problem? Here, L is not Halting problem or Hilbert's tenth problem (because we proved that ... 2answers 948 views ### PCP undecidability There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here: https://en.wikipedia.org/wiki/Post_correspondence_problem I'll assume whoever will ... 1answer 41 views ### How to start solving this type of exercise: Determine if$L$is in$RE\setminus coRE$or$coRE\setminus RE$or$R$or not in$RE\cup coRE$? I'm asking this, because in every exercise I check if I can relate it to one of the things I know, like:$A_{TM}$,$\overline{A_{TM}}$,${HALT_{TM}}$,$\overline{HALT_{TM}}$,$E_{TM}$,$\overline{E_{...
I came across following problem: Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine $L_1 =\{M|M$ accepts at most 2016 strings$\}$ $L_2=\{M|M$ accepts at least 2016 strings$\}$ ...