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

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

(р е к у р с и в н а я р е а л и з у е м о с т ь) – понятие, лежащее в основе предложенного С. К. Клини (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.

- один из видов неклассич. интерпретаций логических и логико математических языков. Различные интерпретации типа Р. определяются по следующей схеме. Для формул логико-математич. языка определяется отношение "объект реализует замкнутую формулу F", к-рое сокращенно записывается . Определение носит индуктивный характер: сначала отношение erF определяется для элементарных формул F, а затем для сложных формул в предположении, что для составляющих их более простых формул это отношение уже определено. Замкнутая формула Fназ. р е а л и з у е м о й, или истинной при данной интерпретации, если существует такой объект е, что erF. Формула F, содержащая свободные переменные x₁, . . ., х _n, считается реализуемой, если реализуема замкнутая формула

Впервые интерпретация такого вида, известная как рекурсивная реализуемость, была предложена С. Кли-ни (см. [1], [2]) с целью уточнения интуиционистской (конструктивной) семантики языка формальной арифметики в терминах рекурсивных функций. Другие понятия Р. являются модификациями рекурсивной Р.

Интуитивный смысл отношения erF такой: объект екодирует информацию об истинности формулы F. Напр., в рекурсивной Р. натуральное число 0 реализует элементарную формулу вида s~i тогда и только тогда, когда эта формула верна (т. е. значения термов s и tсовпадают); если число ереализует дизъюнкцию , то по нему можно выяснить, какой ее член реализуем, и найти число, его реализующее; по числу, реализующему формулу , можно построить алгоритм, к-рый по любому натуральному числу пстроит реализацию формулы А(n). В качестве реализаций, т.е. объектов, реализующих формулы, чаще всего выступают натуральные числа. Однако при интуиционистской интерпретации языка математич. анализа в качестве реализаций могут использоваться и другие объекты, напр. одноместные теоретико-числовые функции (см., напр., [3]).

Для формул логич. языков, напр. для пропозициональных или предикатных формул, Р. определяется обычно через понятие Р. для того или иного логико-математич. языка W. Логич. формула считается реализуемой, если реализуема всякая формула языка Wполучающаяся подстановкой в формул языка W вместо предикатных переменных.

Интерпретации типа Р. нашли широкое применение в исследовании неклассических, прежде всего интуиционистских и конструктивных, логических и логико-математич. теорий. Имеется описание различных понятий Р. и их применений в теории доказательств для исследования интуиционистских теорий (см. [3], [4]).

Лит.:[1] К 1 е е n е S. С., "J. Symbolic Logic", 1945, V. 10, р. 109-24; [2] К л и н и С. К., Введение в метаматематику, пер. с англ., М., 1957; [3] К л и и и С., В е с л и Р., Основания интуиционистской математики..., пер. с англ., М., 1978; [4] Д р а г а л и н А. Г., Математический интуиционизм. Введение в теорию доказательств, М., 1979. В. Е. Плиско.