О вычислительных аспектах максимальной специфичности в вероятностном объяснении

В настоящей статье изучаются вычислительные аспекты формального требования максимальной специфичности, накладываемого на правила в языке пропозициональной классической логики, когда над этим языком задана вычислимая рационально-значная вероятностная мера. Доказана неразрешимость ряда общих проблем по обнаружению максимально специфичных правил и вероятностных мер, для которых совокупность всех специфичных правил вычислима; установлена разрешимость множества максимально специфичных правил при неких естественных ограничениях; исследован вопрос о возможности равномерного нахождения разрешающих процедур в случае упомянутых ограничений; оценена сложность введённых подклассов мер в арифметической иерархии.