ИСТИНА

А.Н. Колмогоров предложил интерпретировать формулы интуиционистской логики как задачи, а интуиционистские связки - как операции над задачами. В дальнейшем были предложены различные формальные уточнения этого подхода. В частности, А.Шень и Н.К.Верещагин предложили измерять сложность задачи наименьшей колмогоровской сложностью ее решения. Был рассмотрен класс формул, при подстановке в которые любых задач вместо переменных сложность возникающей задачи ограничена сублинейной, логарифмической или константной функцией от сложностей подставляемых задач. Во всех случаях получалась логика Янкова (логика слабого закона исключенного третьего). Кроме того, А.Н. Колмогоров выражал идею рассмотрения "единого логического аппарата, имеющего дело с объектами двух типов - высказываниями и задачами". В докладе излагаются некоторые результаты в этом направлении.