Questions tagged [decidability]
The decidability tag has no usage guidance.
4
questions
0
votes
0answers
18 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
34 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
43 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
26 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 ...
