Article collection "Mathematical Problems of Cybernetics" №2, Moscow, 1989
The undecidability of modal logic expressibility problem
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 S4 logic or the D* logic or any other modal logic that lies between those two. This implies that the logic S4, the logic D* and all intermediate modal logics are expressibility-wise undecidable. Also no extension of the S4 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 S4 logic is decidable if and only if it is a locally tabular logic.