The article deals with the expressibility problem in modal logics. We prove that there is no algorithm that can solve the expressibility problem for the S₄ logic or the D* logic or any other modal logic that lies between those two. This implies that the logic S₄, the logic D* and all intermediate modal logics are expressibility-wise undecidable. Also no extension of the S₄ logic, besides locally tabular logics, is expressibility-wise decidable. Another major result of the article is the proof that a finitely axiomizable extension of the S₄ logic is decidable if and only if it is a locally tabular logic.

mathematical logic, modal logics, expressibility problem, S4 logic, tabular logic

Mathematical problems and theory of numerical methods