ИСТИНА

Доказано, что коммуникационная сложность задачи приближения колмогоровской сложности пары слов примерно равна длине этих слов. Найдено преобразование коммуникационных протоколов с частными случайными битами в протоколы с общими случайными битами с наименьшим увеличением разглашаемой информации. Доказано, что для любого тотального алгоритма, который по любой программе слова находит список слов, содержащий почти минимальную программу для этого слова, размер списка должен быть экспоненциального от длины слова размера. Получен ряд результатов о локальной табличности и финитной аппроксимируемости полимодальных логик, в частности, произведений. Рассматривается фрагмент языка модальной логики, состоящий из импликаций A->B, где формулы A и B строятся из пропозициональных переменных и константы «истина» лишь с помощью конъюнкции и модальностей типа ромб. Такой фрагмент называем строго позитивным. Сформулировано арифметически полное исчисление с модальностями, занумерованными натуральными числами и символом омега, где омега соответствует полной равномерной схеме рефлексии в арифметике, а натуральное чимло n соответствует ограничению этой схемы арифметическими Пn+1-предложениями. Для этого исчисления установлена теорема о полноте относительно подходящего класса конечных шкал Крипке, доказана полиномиальная разрешимость проблемы выводимости, а также теорема об арифметической полноте, аналогичная известной теореме Р. Соловея для стандартной логики доказуемости. Предъявлен способ преобразования контекстно-свободной грамматики в форме Хомского в грамматику Ламбека без умножения, сохраняющий структуру деревьев разбора и семантическую разметку выводимых слов. Построены исчисления гильбертовского (несеквенциального) типа для исчисления Ламбека с двумя делениями и исчисления Ламбека с одним делением, допускающего пустые левые части секвенций.