Skip to main content

Questions tagged [decidability]

The tag has no usage guidance.

24 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1 vote
1 answer
40 views

Why we can reduce $A_{TM}$ to $ALL_{CFG}$, but we can not reduce $A_{TM}$ to $E_{CFG}$

If a $PDA$ can be constructed to check whether a string is not a computation history for a Turing Machine. Like in the proof of $ALL_{CFG}$ is not decidable. Then we can construct a $PDA$ that accepts ...
Air Homely's user avatar
1 vote
1 answer
50 views

Reduction from $ALL$ to $DECIDE$

Let $DECIDE=${$<M> :\ M\ halts\ on \ all \ inputs$} and I wish to show its unrecognizable using a reduction from $ALL=${$<M> :L(M)=\Sigma ^* $} using a deterministic turing machine $R$ ...
Aishgadol's user avatar
  • 355
1 vote
0 answers
35 views

How much is decidability compromised within this restriction of the fixpoint combinator?

Though purely functional programming languages, such as Haskell, is commonly thought to have no side-effects, there is a caveat: Recursive calls may hang. I considered this to be undesirable, and ...
Dannyu NDos's user avatar
1 vote
0 answers
55 views

Turing-reducibility for guaranteed decider

The following exercise is taken from Theoretical Computer Science by Atiba. Use Rice's theorem to demonstrate that every decidable language is Turing reducible to some language that is already ...
jase's user avatar
  • 11
1 vote
2 answers
339 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 ...
user149788's user avatar
1 vote
0 answers
55 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 $$\...
Stecco's user avatar
  • 201
1 vote
0 answers
50 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 ...
Omid Yaghoubi's user avatar
1 vote
0 answers
92 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 ...
Hugolin Bergier's user avatar
0 votes
1 answer
39 views

Decide if some DFA is accepted

Given Some(DFA) = {|A is a DFA and L(A) is not empty and L(A) is not equal to Σ^(*)} Show Some(DFA) is decidable. I produced the following answer and wanted to check if I am correct T="On input ...
keth's user avatar
  • 1
0 votes
0 answers
18 views

General rules to tell if a language is regular/CFL/decidable/recognizable

I've been looking online for quite some time for some 'general' rules on this. for example, there's a 'rule' that claims that if a language is like $$L={w\in {a,b,c}^* : count_\alpha (w) =count_\beta (...
Aishgadol's user avatar
  • 355
0 votes
1 answer
114 views

Mapping Reduction from HALT?

I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
Diode's user avatar
  • 1
0 votes
1 answer
70 views

A program that solves the Halting Problem for programs with N states

My question relates to the conclusions drawn from the Halting Problem. I understand that the Halting Problem proves that no program H(P,i) exists that determines if P(i) halts or not for P in general. ...
Vincenzo Buselli's user avatar
0 votes
0 answers
24 views

Reduce A ∶= {x ∈ N ∣ x < 10} to Halting Problem on empty tape

I am preparing for an exam in computability and still learning about the idea of reductions. I found an interesting problem to start with and am curious if my approach is correct: Let H0 be the ...
dport's user avatar
  • 1
0 votes
1 answer
95 views

Proving a language is recursively enumerable

Prove that the following language is recursively enumerable: L = {<M,x> | Turing machine M enters the same configuration twice on input x} I have tried to construct a TM that maintains the ...
revision's user avatar
0 votes
0 answers
30 views

How can decidability/semi-decidability/undecidability have impact on REAL life applications/examples?

How decidability/semi-decidability/undecidability has impact on REAL life applications/examples? I understand that it can be used for implementation of various algorithms but what else?
Arthemoon's user avatar
  • 141
0 votes
0 answers
169 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 <...
Tommasosp13's user avatar
0 votes
2 answers
3k 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 $$\...
Stecco's user avatar
  • 201
0 votes
0 answers
46 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$, ...
Matthias K.'s user avatar
0 votes
0 answers
165 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, ...
ali rezaei's user avatar
0 votes
0 answers
79 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 ...
yemen's user avatar
  • 3
0 votes
0 answers
40 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 ...
user6394019's user avatar
0 votes
0 answers
54 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 ...
Ayush's user avatar
  • 117
-1 votes
1 answer
47 views

Prove that $L = \{ \langle M \rangle | \text{ M is a PDA, L(M) contains at least 1 string w that } |w| \leq n \}$ is recursive?

Description Similar to the encoding of a Turing Machine, we can encode a Push-Down Automata. Denote $\langle M \rangle$ as the encoding of PDA M, and a natural number n, is language $L = \{ \langle M \...
Morphlng's user avatar
-2 votes
1 answer
43 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?
Bubino's user avatar
  • 111