Философская энциклопедия - реализуемость

РЕАЛИЗУЕМОСТЬ

(р е к у р с и в н а я р е а л и з у е м о с т ь) – понятие, лежащее в основе предложенного С. К. Клини (1945) метода конструктивного (интуиционистского) понимания матем. (и логич.) предложений, к-рый позволяет в точных терминах говорить об их "истинности" и является, т.о., попыткой построения конструктивной семантики. Проблема конструктивного истолкования матем. суждений была поставлена еще А. Колмогоровым (1932, см. Исчисление задач), но из-за отсутствия в то время точного понятия алгоритма в колмогоровской интерпретации оставались моменты неясные, допускающие неоднозначное толкование. Идея метода Клини может быть прослежена, исходя из: 1) интуиционистского понимания экзистенциального суждения вида ∃хА (х) как неполного сообщения, к-рое может быть "восполнено" указанием нек-рого х, такого, что А (х) и, вообще говоря, дальнейшей "информацией", нужной для восполнения сообщения А (х) для этого х (если А (х), также является неполным сообщением); понимания импликации A⊃B как неполного сообщения, восполняемого путем задания эффективного общего метода получения информации, восполняющей В, по данной информации, восполняющей А, и аналогично для др. логич. операций; 2) идеи арифметизации (эффективной нумерации), посредством к-рой любая "информация" может быть задана в виде чисел (см. Метатеория; это, по существу, та самая, исходящая от К. Гёделя, идея, к-рая была положена в практич. приложениях кибернетики в основу кодирования информации для вычислит. машин); 3) экспликации "эффективных" методов задания "информации" (к-рая, согласно (2), может быть числовой) в виде "рекурсивных" методов определения и доказательства (см. Определение, раздел Рекурсивные и индуктивные определения, Рекурсивные функции и предикаты). Сочетание этих идей, вместе с признанием возможности "непосредственной проверки" элементарных арифметич. формул вида а = b, где а и b – постоянные (осуществляемой попросту вычислением значений термов а и b), привело Клини к формулировке след. понятия р е к у р с и в н о й Р.: 1. Натуральное число е реализует элементарную замкнутую (далее всюду А и В замкнутые формулы) арифметич. формулу а = b, если е = 0 и значение а равно значению b. 2. е реализует А&В, если e=2а·3^b, где а реализует А и b реализует В. 3. е реализует AVB, если e = 20·3^a, где а реализует А, или 2¹3^b, где b реализует B. 4. е реализует А⊃B, если е есть гёделев номер частично-рекурсивной функции φ от одной переменной, такой, что если а реализует А, то φ (а) реализует В. 5. е реализует А, если е реализует А⊃1 = 0. 6. е реализует ∃xA (x) (где x – переменная, а А (х)) формула, не содержащая никаких свободных переменных, кроме, быть может, х), если е = 2t·3a, где а реализует A (t). 7. е реализует ∀хА (х) (при тех же условиях на А (х) и х), если е есть гёделев номер общерекурсивной функции от одной переменной, такой, что для каждого натурального t число φ (t) реализует A(t).

Формула А, не содержащая свободных переменных, реализуема, если существует число р, реализующее А. Формула А (у1, ..., ym), содержащая свободно только переменные y1, ..., уm (m > 0), отличные друг от друга, наз. (рекурсивно) реализуемой, если существует общерекурсивная функция φ от m переменных такая, что для каждого набора натуральных чисел t1, ..., tm число φ (t1, ..., tm) реализует A (t1, , tm). Наконец, понятие Р. естеств. образом распространяется и на формулы логики высказываний: пропозициональная формула наз. реализуемой, если реализуема всякая арифметич. формула, получающаяся из нее путем подстановки.

Клиниевское понятие Р. (совпадающее с точностью до способа задания и нек-рых уточнений с рассматриваемым Н. А. Шаниным (1955) понятием в о с п о л н е н и я) положило начало обширному циклу исследований (работы самого Клини, амер. математиков Д. Нельсона и Дж. Роуза, сов. математиков Н. А. Шанина, Ю. Т. Медведева, Н. М. Нагорного, В. А. Янкова, Ф. А. Кабакова и др.), в ходе к-рых были предложены и др. модификации этого понятия. Выяснилось (Дж. Роуз, 1953), что имеются реализуемые, но не выводимые в конструктивном (интуиционистском) исчислении высказываний формулы (в то время как любая доказуемая формула этого исчисления реализуема), т.е. что конструктивное исчисление высказываний неполно (см. Полнота) относительно понятия Р. (Термин "Р." имеет в математике и матем. логике и др. значение: он употребляется как синоним для "интерпретируемости", т.е. наличия модели, или "реализации".)

Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957, § 82 (есть библ.); Шанин Η. Α., О некоторых логических проблемах арифметики, "Тр. Матем. ин-та АН СССР", 1955, т. 43 (есть библ.); его же, О конструктивном понимании математических суждений, там же, 1958, т. 52 (есть библ.).

Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960—1970.