ИСЧИСЛЕНИЕ ЗАДАЧ

интуиционистское исчисление высказываний, понимаемое в свете интерпретации, к-рую предложил в 1932 сов. ученый А. Н. Колмогоров. Эта интерпретация была свободна от гносеологич. установок интуиционизма и вскрывала содержательный материалистич. смысл указ. исчисления. При интерпретации Колмогорова значениями переменных в формулах являются любые з а д а ч и. Если р и q задачи, то формулы р & q, p / q, p ? q и р толкуются, соответственно, как задачи: "Решить задачу p и задачу q", "Решить задачу p или задачу q", "Свести решение задачи q к решению задачи р" и "Предполагая задачу p решенной, прийти к противоречию". Эта интерпретация положила начало разработке принципов конструктивного понимания логич. связей и конструктивного истолкования суждений логики и математики. При интерпретации Колмогорова каждой доказуемой формуле U (р1, р2, ..., рn) интуиционистского исчисления высказываний (см. Интуиционистская логика) соответствует класс задач, имеющих общий метод решения (не зависящий от конкретного содержания задач р1, р2, ..., рn). Формуле же p / р не доказуемой в указ. логич. исчислении (она выражает принцип исключенного третьего), соответствует класс задач вида "Решить задачу p или, предполагая задачу p решенной, прийти к противоречию", существование общего метода решения к-рых как раз не очевидно. В интерпретации Колмогорова оставалось не выясненным, что надо понимать под общим методом решения задач нек-рого класса и под свед?нием решения одной задачи к решению другой. Это было уточнено (и притом различными способами) после того, как в 30-х гг. были разработаны точные понятия алгоритма и вычислимой (рекурсивной) функции (см. Рекурсивные функции и предикаты), что позволило строго доказать несуществование общего метода (алгоритма) решения задач из класса, соответствующего формуле p / р. Действительно, существование такого алгоритма означало бы, в частности, существование алгоритма решения задач вида "Доказать выводимость формулы U в исчислении S или, предполагая формулу доказуемой в нем, прийти к противоречию" (в качестве p взята задача "Доказать выводимость U в исчислении S"). Алгоритм решения задач этого вида при нек-ром конкретном S является решением разрешения проблемы для исчисления S. Но, как показал Черч (1936), эта проблема неразрешима, напр., для узкого исчисления предикатов. Идеи Колмогорова получили развитие в работах Клини (1945) (см. Реализуемость), Медведева (1955), Шанина (1958). См. Конструктивная логика. Лит.: Пильчак Б. Ю., Об исчислении задач, "Укрмат. ж.", 1952, т. 4, No 2, с. 174–94; ее же, О проблеме разрешимости для исчисления задач, "Докл. АН СССР", 1950, т. 75, No 6, с. 773–76; Медведев Ю. Т., Степени трудности массовых проблем, там же, 1955, т. 104, No 4, с. 501–504; Шанин ?. ?., О конструктивном понимании математических суждений. "Тр. мат. ин-та им. В. А. Стеклова", 1958, т. 52, с. 226–311; его же, Об алгорифме конструктивной расшифровки математических суждений, "Z. Math. Logic und Grundlagen der Math.", 1958, Bd 4, H. 3, S. 293–303; Клини С. К., Введение в метаматематику, пер. с англ., М., 1957, § 82; Коlmоgоrоff ?., Zur Deutung der intuitionistischen Logik, "Math. Z.", 1932, Bd 35, S. 58–65; Church ?., A note on the Entscheidungsproblem, "J. Symb. Logic", 1936, v. 1, No 1, p. 40–41; Кleene S. С., On the interpretation of intuitionistic number theory, там же, 1945, v. 10, No 4, p. 109–24. Б. Пильчак. Москва.