this question is inspired by a recent popular question  on a boundary relating to decidable and undecidable problems (ie open problems in this area), a sort of counterpoint. there are at least ...
It is known that first order logic is too general to be decidable. Adding axioms with special meaning (e.g. expressing notions such as necessity/obligation, provability, etc.) leads us to modal logics ...
It is known that many logic problems (e.g. satisfiability problems of several modal logics) are not decidable. There are also many undecidable problems in algorithm theory, e.g. in combinatorial ...
There are problems that are decidable, there are some that are undecidable, there is semidecidability, etc. In this case I wonder whether a problem can be meta-undecidable. This means (at least in my ...
consider two similar pieces of (pseudo)code: A: n = f(x) for (i = 1 to n) do begin .... end B: x = 1 while (x != 0) do begin x = g(x) .... end in case A if ...
What are the ways in which one can add a decidable equivalence relation in a type system with undecidable type checking/extensional equality?
CFG here stands for context-free grammar. I understand that: Deciding whether a CFG $G$ is ambiguous is undecidable. Deciding whether a CFL $L$ is inherently ambiguous is undecidable. My question ...
Answer: not known. The questions asked are natural, open, and apparently difficult; the question now is a community wiki. Overview The question seeks to divide languages belonging to the ...