Questions tagged [decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
28 views

If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?

I was learning about decidability when I thought of this question: If P is partially decidable, is ¬P decidable, partially decidable or undecidable? I think it is Undecidable since if ¬P holds then P ...
user avatar
1 vote
1 answer
93 views

Language of Turing machines that go through some configuration infinitely many times on empty input

I've been going through some questions on old homework. Here was a question that confused me somehow. Question: Given a language $$L=\{\langle M\rangle\ |\ M \text{ is a Turing machine. } M \text{ ...
user avatar
0 votes
1 answer
70 views

Decidability of a context free Grammar

Say that a Context Free Grammar is red when it accepts every word of length 3 that begins with a, and extremely red when it accepts every word that begins with a. Is redness decidable? or Semi ...
user avatar
1 vote
1 answer
57 views

A decidable language that can't be decided by a circuit ensemble of linear size

Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C_i for every natural i s.t input size is i) such that every circuit's size is linear (in input ...
user avatar
0 votes
0 answers
21 views

Prove that the problem of REGEX producing strings with 111 as substring is decidable

I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Given <...
user avatar
1 vote
1 answer
60 views

For any two languages A and B there exists J such that both A and B are Turing reducible to J

Here is the my attempt: Proof : Suppose $J = \{aa' \mid a \in A\} \cup \{bb' \mid b \in B\}$ such that $a'$ and $b'$ are the symbols that do not belong to any $w \in A \cup B$ and $a,b$ are strings. ...
user avatar
1 vote
0 answers
123 views

Prove that determining if a PDA has an infinite language is decidable

I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Given $$\...
user avatar
  • 181
1 vote
0 answers
47 views

Prove that the problem of CFG producing epsylon is decidable

I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Given $$\...
user avatar
  • 181
0 votes
0 answers
90 views

Show that ALL DFA is decidable

I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Given $$\...
user avatar
  • 181
2 votes
1 answer
63 views

A language of natural numbers is decidable iff it is either finite or the image of some strictly increasing computable function

Suppose $L \subseteq \mathbb N$ such that, for the purpose of Turing machine computation, numbers in $L$ are represented by strings over the alphabet $\{0, 1\}$ in the standard binary notation. Prove ...
user avatar
1 vote
0 answers
37 views

Does description method matter in Rice’s theorem?

If $\mathcal{p}$ is a nontrivial property of formal languages, then $L_{\mathcal{p}} = \{ \langle M \rangle \mid L(M) \in \mathcal{p} \}$ is undecidable by Rice’s theorem. What if we describe ...
user avatar
-2 votes
1 answer
34 views

Decision problem

Prove the following theorem Let A and B be two languages on an alphabet Σ. If A ≤p B and B ∈ P, then A ∈ P. Could anyone be able to prove it?
user avatar
  • 1
2 votes
1 answer
159 views

Useless states in a PDA

I am trying to solve a problem in Sipser's Introduction to the Theory of Computation book, which reads: 4.22 A useless state in a pushdown automaton is never entered on any input string. Consider the ...
user avatar
  • 123
0 votes
1 answer
16 views

Show that $ Y \subseteq A^*$ is decidable

Let A be a nonempty alphabet, $X ⊆ A^*$ a decidable set, and $Y ⊆ A^*$ be a semi-decidable set. We assume that $Y ⊆ X$ and that $X \setminus Y ⊆ A^*$ is semi-decidable. Show that then the set Y ⊆ A∗ ...
user avatar
  • 3
0 votes
0 answers
36 views

If $L_1 \leq_m L_2$, and $L_2$ is decidable, is $L_1$ then decidable?

There is a lemma in our textbook that asks us to prove the following: If $L_1 \leq_m L_2$, and $L_2$ is decidable, then $L_1$ is decidable I tried proving this by saying that if $L_1 \leq_m L_2$, ...
user avatar
0 votes
1 answer
43 views

Can 3-SAT be recognized in less than exponential time?

Obviously it is an open question if $3$-SAT can be decided in a polynomial amount of time. But what results do we know about its recognizabilty? Can $3$-SAT be recognized in a polynomial amount of ...
user avatar
  • 147
0 votes
0 answers
55 views

Decidability of the language of a regular expression being a subset of a given context free language

Let L be a language of pairs $\langle R,G\rangle$, with the first element being a regex and the second being a CFG. Is it decidable that G accepts whatever the regular expression does? In other words, ...
user avatar
0 votes
0 answers
51 views

Complement of a context free language

Consider the context-free language of balanced parentheses of three kinds: $$L = \{w \in \{ (, ), [,], \{, \} \}^∗ \mid \text{all parentheses in }w \text{ are properly balanced}\} $$ What will be the ...
user avatar
  • 3
1 vote
1 answer
62 views

Decidability for intersection of context free and regular languages

I am wondering if the following are decidable or undecidable and why. L is a CFL and R is a regular language. How does the complement of the context-free language change the decidability of the ...
user avatar
0 votes
0 answers
20 views

Is there any problems with equating Turing Machines with Algorithms and Language with Problems?

In a lot of the online explanation of complexity theory, the author proposes the following. "The definition associated with complexity theory (e.g., definition of NP) is phrased in terms of ...
user avatar
-1 votes
1 answer
45 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 ...
user avatar
  • 1
0 votes
1 answer
111 views

Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?

Context-sensitive languages have context-sensitive grammars, and context-free languages have context-free grammars. Using context-free grammars, we can decide the finiteness and emptiness of context-...
user avatar
  • 1
0 votes
0 answers
34 views

Why linear bounded automata emptiness and finiteness isn't decidable? [duplicate]

We know that linear bounded automata has tape size based on input size which is limited. Context-sensitive languages are accepted by LBA. My question is that if LBA has limited tape size why it's ...
user avatar
  • 1
0 votes
1 answer
204 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 ...
user avatar
  • 1
0 votes
0 answers
67 views

Whether $L(G)=L(R)$ is decidable for DCFL and CFL?

Let $G_1$ be the context free grammar and $R$ be regular language. Now I have to check whether $L(G_1)=L(R)$ is decidable or not? My approach $\overline{L(G_1)}=\overline{L(R)}$. Now $L(G_1)$ not ...
user avatar
  • 1
0 votes
1 answer
114 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 ...
user avatar
  • 1
0 votes
2 answers
220 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 ...
user avatar
  • 1
0 votes
1 answer
80 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?
user avatar
  • 1
0 votes
1 answer
79 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 ...
user avatar
  • 1
0 votes
0 answers
34 views

Is this language in RE?

Given the following language: $$L=\left \{ <M> | \exists L \in R \quad s.t \quad L(M)\subseteq L \right \}$$ I need to determine it's compuation class(R or RE). I used Rice Theorem as follows to ...
user avatar
0 votes
0 answers
23 views

Loop in control flow graph of a program versus checking whether program goes into infinite loop or not

Which of these is true or false. 1)If Control Flow graph(CFG) doesn't contain any loop, the program will never go into infinite loop. 2)If CFG contains loop, the program may or may not go into ...
user avatar
  • 107
-1 votes
1 answer
53 views

How to determine whether this language is regular?

I've encountered this question recently: Given $\Sigma=\{\sigma_1, \sigma_2, ..., \sigma_n\}$ and $n\ge 2$, determine whether the following language is regular or not: $$ L_1=\{w\in\Sigma^*|for \ 1 \...
user avatar
0 votes
1 answer
39 views

Prove decidable

L={⟨M⟩: M is a DFA and for each string in L(M) the number of 1s is more than or equal to the number of 0s } T = "On input where M is encoded DFA" ...
user avatar
0 votes
0 answers
39 views

The role of diagonalization - asymmetry between TM and Recursion Theory

This might be a slightly strange or irrelevant question. My apologies if it is. I'll try to formulate it the best I can. First, here is an hypothesis: diagonalization is syatematically used to prove ...
user avatar
3 votes
1 answer
47 views

Effectively decidable vs. noneffectively (or ineffectively) decidable

The introduction of https://www.sciencedirect.com/science/article/pii/0001870882900482 starts with the following sentence: The word problem for commutative semigroups is effectively decidable. I ...
user avatar
1 vote
2 answers
151 views

Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable

So I want to prove that $$ \big\{\langle M \rangle : \text{ M is a TM and } L(M) \text{ is decidable} \big\}$$ is undecidable. To do so I want to reduce it from$\ \overline{A_{TM}}$ with a function ...
user avatar
  • 31
1 vote
1 answer
48 views

Decidability of $\{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ \Sigma^+$}\}$

I want to prove that the following language is decidable: $$\mathit{SEQ}_{\mathit{CFG}} = \{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ L$}\}, \text{ where } L = \Sigma^* - \{\epsilon\}$$ So, I think about ...
user avatar
  • 75
-5 votes
1 answer
408 views

Could H correctly decide that P never halts?

Because a halt decider must compute the mapping from its inputs to an accept or reject state on the basis of the actual behavior of its actual inputs, when H is a simulating halt decider H(P,P) would ...
user avatar
  • 121
4 votes
1 answer
1k views

A language is Turing recognizable iff it is a projection of a decidable language

I was wondering how to prove that a language $C$ is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$. I do not know how to ...
user avatar