Questions tagged [decidability]
The decidability tag has no usage guidance.
8
questions
0
votes
0answers
27 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 ...
0
votes
0answers
14 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 ...
-1
votes
1answer
46 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 \...
0
votes
1answer
28 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"
...
0
votes
0answers
22 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 ...
2
votes
1answer
41 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 ...
1
vote
2answers
59 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 ...
1
vote
1answer
30 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 ...
