Article collection "Mathematical Problems of Cybernetics" №2, Moscow, 1989

Authors:Raţă M.F.

The undecidability of modal logic expressibility problem

Abstract:

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_{4} logic or the D* logic or any other modal logic that lies between those two. This implies that the logic S_{4}, the logic D* and all intermediate modal logics are expressibility-wise undecidable. Also no extension of the S_{4} 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_{4} logic is decidable if and only if it is a locally tabular logic.