# Questions tagged [undecidability]

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

882 questions
Filter by
Sorted by
Tagged with
27 views

194 views

### Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the ...
1 vote
38 views

### Is the Language of all encodings of Turing Machine that at least halts on one input and outputs 0 semi-decidable?

I need to prove if the following Language is or is not semi-decidable. A := {w ∈ {0,1}^* | there exists an input x on which M_w produces the output 0} Where A is the language of all the encoding w ∈ {...
1 vote
985 views

### Determine if a language is Decidable or semi decidable

Consider the language $L = \{\langle M \rangle: \text{$M$accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$. We need to determine, without ...
118 views

### Help understanding the proof that $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$ is undecidable

I understand of the existence of Rice's Theorem, however, I want to understand better how this reduction is formed. My professor gives the answer as follows: "By contradiction, assume that $L$ is ...
62 views

### Is the "intersection" of the special Halting Problem with a language always undecidable?

I'm exploring the decidability characteristics of a particular language formed by the intersection of two languages, specifically in the context of the Halting Problem. The languages are defined as ...
53 views

### Is explicitly explaining the case where the Turing Machine loops forever essential to proving reducibility?

I am asking this in the context of the following question: Let N be a non-deterministic Turing Machine. We say that N faces a dilemma if at some point in its working, it encounters a situation where ...
129 views

### Deciding whether a Turing machine decides a language $L$ in at most $n^2$ steps

Let $L$ be a language for which there exists some turing machine deciding it in at most $n^2$ steps. Is it decidable whether a given turing machine $M$ decides $L$ and runs in at most $n^2$ steps? I ...
45 views

1 vote
40 views

### Reformulating the Given Conditions in Decidability Problems

I came across the following question: Given two context-free languages $L_1$ and $L_2$ is it decidable whether $L_1 - L_2 = \emptyset$ ? The problem $ALL_{\text{CFG}}$ that states: Given a CFG $G$ ...
1 vote
114 views

### Is the problem of Proper Subset of decidable languages decidable?

Given 2 recursive - decidable languages $L_1$ and $L_2$ is the problem $L_1 \subset L_2$ solvable - decidable? Since both $L_1$ and $L_2$ are recursive - decidable there exist Turing Machines say $M_1$...
26 views

### Question regarding rice theorem

this is a question I got from a test that we had before Let there be X, a subgroup of languages above $\Sigma$ such that X isn't empty nor all of the langauges in $\Sigma$ we need to say if the ...
20 views

### proving or disproving a reduction from $R \leq P(Σ^*) \backslash RE$

I need to prove or disprove that for all languages in $R$ there is a reduction to all languages in $P(Σ^*)\backslash RE$. And I'm having trouble to figuring out the solution, especially with dealing ...
620 views

### Are the halting problem proofs refuted by software engineering?

Can D simulated by H terminate normally? The x86utm operating system based on an open source x86 emulator. This system enables one C function to execute another C function in debug step mode. When H ...
206 views

### Proof: is the language $L_1=\{\langle M\rangle\mid\emptyset \subseteq L(M)\}$ (un)-decidable?

I want to show that $L_1 = \{\langle M\rangle \mid \emptyset \subseteq L(M)\}$ is decidable/undecidable - without rice theorem (just for the case that I can apply it). Every language contain the \$\...
61 views

### Undecidability of syntactic properties

Rice's theorem comments on the undesirability of non-trivial semantic properties, however there are syntactic properties that are undecidable as well, such as the "useless" states problem ...