# Questions tagged [undecidability]

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

752 questions
Filter by
Sorted by
Tagged with
53 views

### Proof of undecideability that one state is reached before another

I'm trying to show that, for a deterministic Turing machine $M=(Q,\Gamma,\Sigma,\delta,q_0)$, the language $K$, which includes all of the words $w \in \Sigma^\ast$ where the calculation of $M$ on $w$ ...
478 views

### Is determining if a Turing machine runs in constant time decidable if one assumes it halts?

As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts? The decision problem, more formally: Given a Turing machine $M$ where it is assumed ...
4k views

### Is the infinite language unrecognizable in a Turing machine?

This question is building up on an older one, here. But now let's say we keep $Σ=\{0,1\}$. Is the TM that accept anys ($1^x \mid x \gt 0$) recognizable? That means 1, 11, 11111, 1111111, and so on ...
234 views

### Is the reverse of a closed under operation maintainable?

I'm looking at the following question from this handout: The class of decidable languages is closed under union My question is, does this hold in reverse? Is there a phrase for this? Basically, if ...
126 views

### Can we enumerate finite sequences which have no halting continuation?

Note: this question has been cross-posted to Math.SE, after about a week here. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
545 views

### A language which is neither r.e. nor co-r.e

First, consider $$L_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$ is RE. I tried to construct a Turing machine: ...
80 views

### Decidability of language of TMs which accept only their Gödel number [duplicate]

I am trying to prove that $L = \{\langle M \rangle \mid L(M) = \{\langle M \rangle \}\}$ is undecidable, where $\langle M \rangle$ is the code of the TM $M$, and $L(M)$ the language recognized by $M$....
102 views

### Rice's theorem applicable to the following language?

Let $L= \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \}$ be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable. I've heard that I can't use Rice's ...
229 views

1k views

### Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
116 views

### Halting problem of TM which recognize recursive languages is undecidable?

I am preparing for an exam and I came across this question in one of the tests. Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False) The solution ...
2k views

### Relation between Undecidable problems and NP-Hard

I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly. And then, I realized that it is not certain where undecidable problems should be placed. ...
148 views

### Is this language recognizable?

Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable. I don't think it's even recognizable, but I'm not sure. Regardless, I ...
114 views

### Context sensitive language is context free

Problem of determining whether a context sensitive language is context free is undecidable. How to prove it
86 views

### Decidability of factoring algebraic equations

Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution: $$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$ And some arbitrary factorization constraints, say:...
55 views

### 3-SAT wher each literal appears at most once [duplicate]

I'm currently following a course and we have to prove that a restricted version of the 3-SAT decision problem where each literal appears at most once is solveable in polynomial time. I think such a ...
694 views

### Whether language of all turing machines is decidable or undecidable or semi-decidable?

I recently came across this language: $L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$ It was asked in the question to find out whether language L is decidable or undecidable. ...
84 views

### Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable

I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $ALLCFG$ is an undecidable language (where $ALLCFG$ means that $G$ is a $CFG$ that ...
382 views

### Reduce ATM to the language of TM encodings where if the TM accepts w then the TM accepts ww

Today I did a test in my class, the trace was: Prove that the language $L =\{\langle M\rangle\mid \forall w \in \{0,1\}^\ast: M \text{ accepts }w\implies M \text { accepts }ww \}$, is undecidable ...
160 views

### Example for an undecidable language L such that L is reducible to its complement and vice versa

I am searching for an undecidable language $L$, such that $L \leq \Sigma^* \setminus L$ and $\Sigma^* \setminus L \leq L$, but I am not able to find a concrete language and reduction. Is there ...
33 views

94 views

### Why did Alan Turing have to define computation before demonstrating undecidability?

It seems to me that Turing could've just presented the following argument: Theorem: Given a computational model $\mathcal{M}$ capable of conditional branching and indeterminate repetition the halting ...
294 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 ...
968 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 ...
89 views

1k views

### Determining if given languages are regular or recursively enumerable

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$\}$ ...
829 views

### Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable

I tried to prove by contradiction. $L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable. L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, ...