# Questions tagged [undecidability]

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

788 questions
Filter by
Sorted by
Tagged with
30 views

### Does Turing machine move left on particular input?

We know that RE language is the collection of unrestricted grammar which is known as type-0 grammar that's why emptiness, finiteness of every RE languages is undecidable. My question is how I check ...
24 views

### TM decidable or undecidable problem?

Question: Explain why the following problems are decidable or undecidable (Using rice's theorem where possible). Does the language accepted by a Turing machine contain an even-length word? Holds a ...
137 views

### Why REC languages is undecidable under emptiness and finiteness?

Membership problem of Recursive languages are decidable. My approach: Let $L$ be a recursive language and $M$ be the Turing Machine that accepts it. For string $w,$ if $w ∈ L,$ then $M$ halts in ...
78 views

### Rice theorem could apply except RE language?

You know that Rice theorem is applicable to check decidability of RE language. Also we know that all regular, deterministic context free, context free, recursive languages are RE languages. $Q_1:$ So ...
116 views

### Regularity of CFG and DCFL

I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$. My ...
31 views

### Why finiteness problem of CFL is decidable?

We know that every $CFL$ has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space?
34 views

### Reasoning given with explanation of Halting Problem

I have read (and re-read) the informal proof of The Halting Problem. Can we not make the same argument using only the Program, without the Input {e.g. H(P) rather than H(P, I)}? I am confused by the ...
75 views

### Reduction from undecidability, decidability to decididabilty

If given any two language both $L_1$ and $L_2$ are decidable then why both $L_1\leq_m^\mathsf{}L_2$ and $L_2\leq_m^\mathsf{}L_1$ are false. Please provide easy explanation with any counterexample ...
67 views

### How to prove that the problem $\text{"If$L$is a context-free language, then, is$\overline{L}$also context-free?"}$ is undecidable?

Lately I came across a problem: $\text{"If$L$is a context-free language, then, is$\overline{L}$also context-free?"}$ And I need to comment on its decidability. Now I know that context free ...
24 views

28 views

### Show that a language is not decidable by reducing from ATM

Let (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM$M$accepts$w$}\}$) show that the language L={<M1,M2,w> | M1 and M2 both accept or reject w} is undecidable by reducing ATM ...
21 views

### Are there decidable non-trivial properties of a LBA's accepted language?

The halting problem and therefore the acceptance problem are decidable for LBAs, but are the infinite extensions of these problems decidable? Given a LBA, can you decide whether there exists an input ...
109 views

### Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem?

Say I'm given an oracle that tells me whether or not $L(M)$, the set of words accepted by a Turing Machine $M$, is finite. By leveraging this oracle, can I solve the halting problem? That is, on an ...
37 views

### A language is decidable iff some enumerator enumerates it in decreasing order [duplicate]

Show that a language is decidable iff some enumerator enumerates the language in decreasing order. What does it mean by enumerator enumerating in decreasing order? I am so confused about this concept....
110 views

### Show that a language is decidable iff some enumerator enumerates the language in decreasing order

Show that a language is decidable iff some enumerator enumerates the language in decreasing order. I know a language is decidable iff some enumerator enumerates the language in the standard string ...