Комбинаторная логика

Логический формализм с использованием комбинаторов вместо переменных

Комбинаторная логика — это обозначение, позволяющее устранить необходимость в количественных переменных в математической логике . Он был представлен Мозесом Шенфинкелем ^[1] и Хаскеллом Карри ^[2] и совсем недавно использовался в информатике в качестве теоретической модели вычислений , а также в качестве основы для разработки языков функционального программирования . Он основан на комбинаторах , которые были представлены Шёнфинкелем в 1920 году с целью предоставить аналогичный способ построения функций и исключить любое упоминание переменных, особенно в логике предикатов . Комбинатор — это функция высшего порядка , которая использует только применение функции и ранее определенные комбинаторы для определения результата на основе своих аргументов.

По математике

Комбинаторная логика изначально задумывалась как «пред-логика», которая должна была прояснить роль количественных переменных в логике, по существу, путем их исключения. Другим способом устранения количественных переменных является логика функторов предикатов Куайна . Хотя выразительная сила комбинаторной логики обычно превышает силу логики первого порядка , выразительная сила логики функторов предикатов идентична силе логики первого порядка (Quine 1960, 1966, 1976).

Первоначальный изобретатель комбинаторной логики Мозес Шенфинкель ничего не опубликовал по комбинаторной логике после своей оригинальной статьи 1924 года. Хаскелл Карри заново открыл комбинаторы , работая преподавателем в Принстонском университете в конце 1927 года ^. логика. Результатом этих исторических случайностей было то, что до тех пор, пока теоретическая информатика не начала проявлять интерес к комбинаторной логике в 1960-х и 1970-х годах, почти все работы по этому предмету велись Хаскеллом Карри и его учениками или Робертом Фейсом в Бельгии . Карри и Фейс (1958), а также Карри и др. (1972) рассматривают раннюю историю комбинаторной логики. Более современную трактовку комбинаторной логики и лямбда-исчисления вместе можно найти в книге Барендрегта ^[4] , в которой рассматриваются модели , разработанные Даной Скотт для комбинаторной логики в 1960-х и 1970-х годах .

В вычислительной технике

В информатике комбинаторная логика используется как упрощенная модель вычислений , используемая в теории вычислимости и теории доказательств . Несмотря на свою простоту, комбинаторная логика отражает многие существенные особенности вычислений.

Комбинаторную логику можно рассматривать как вариант лямбда -исчисления , в котором лямбда-выражения (представляющие функциональную абстракцию) заменяются ограниченным набором комбинаторов , примитивных функций без свободных переменных . Лямбда-выражения легко преобразовать в выражения-комбинаторы, а сокращение комбинатора намного проще, чем сокращение лямбда-выражений. Следовательно, комбинаторная логика использовалась для моделирования некоторых нестрогих функциональных языков программирования и аппаратного обеспечения . Самой чистой формой этого представления является язык программирования Unlambda , единственными примитивами которого являются комбинаторы S и K, дополненные вводом/выводом символов. Несмотря на то, что Unlambda не является практическим языком программирования, он представляет некоторый теоретический интерес.

Комбинаторная логика может иметь множество интерпретаций. Многие ранние статьи Карри показали, как перевести наборы аксиом традиционной логики в уравнения комбинаторной логики. ^[5] Дана Скотт в 1960-х и 1970-х годах показала, как объединить теорию моделей и комбинаторную логику.

Краткое изложение лямбда-исчисления

Лямбда-исчисление связано с объектами, называемыми лямбда-термами , которые могут быть представлены следующими тремя формами строк:

• ${\displaystyle v}$
• ${\displaystyle \lambda v.E_{1}}$
• ${\displaystyle (E_{1}E_{2})}$

где — имя переменной, взятое из предопределенного бесконечного набора имен переменных, а и — лямбда-термины. ${\displaystyle v}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{2}}$

Члены формы называются абстракциями . Переменная v называется формальным параметром абстракции и является телом абстракции. Термин представляет собой функцию, которая при применении к аргументу связывает формальный параметр v с аргументом, а затем вычисляет результирующее значение — то есть возвращает , при этом каждое вхождение v заменяется аргументом. ${\displaystyle \lambda v.E_{1}}$ ${\displaystyle E_{1}}$ ${\displaystyle \lambda v.E_{1}}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{1}}$

Условия формы называются приложениями . Вызов или выполнение функции модели приложения: функция, представленная символом , должна быть вызвана с аргументом в качестве аргумента и вычислен результат. Если (иногда называемый приложением ) является абстракцией, термин можно сократить : аргумент можно подставить в тело вместо формального параметра , и результатом будет новый лямбда-термин, который эквивалентен старому один. Если лямбда-терм не содержит подчленов формы, то его нельзя сократить и говорят, что он находится в нормальной форме . ${\displaystyle (E_{1}E_{2})}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{2}}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{2}}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{1}}$ ${\displaystyle ((\lambda v.E_{1})E_{2})}$

Выражение представляет собой результат взятия термина E и замены в нем всех свободных вхождений v на a . Таким образом мы пишем ${\displaystyle E[v:=a]}$

${\displaystyle ((\lambda v.E)a)\Rightarrow E[v:=a]}$

По соглашению мы используем сокращение для (т. е. приложение остается ассоциативным ). ${\displaystyle (abc)}$ ${\displaystyle ((ab)c)}$

Мотивацией такого определения редукции является то, что оно отражает основное поведение всех математических функций. Например, рассмотрим функцию, которая вычисляет квадрат числа. Мы могли бы написать

Квадрат х равен ${\displaystyle x*x}$

(Использование « » для обозначения умножения.) Здесь x — формальный параметр функции. Чтобы оценить квадрат для определенного аргумента, скажем, 3, мы вставляем его в определение вместо формального параметра: ${\displaystyle *}$

Квадрат 3 это ${\displaystyle 3*3}$

Чтобы вычислить полученное выражение , нам пришлось бы прибегнуть к нашим знаниям об умножении и числе 3. Поскольку любое вычисление представляет собой просто композицию оценки подходящих функций по подходящим примитивным аргументам, этого простого принципа замены достаточно, чтобы уловить основной механизм расчет. Более того, в лямбда-исчислении такие понятия, как '3' и ' ', могут быть представлены без необходимости использования внешних примитивных операторов или констант. В лямбда-исчислении можно идентифицировать термины, которые при правильной интерпретации ведут себя как число 3 и как оператор умножения, см. Кодирование Чёрча . ${\displaystyle 3*3}$ ${\displaystyle *}$

Известно, что лямбда-исчисление по вычислительной мощности эквивалентно многим другим правдоподобным моделям вычислений (включая машины Тьюринга ); то есть любой расчет, который может быть выполнен в любой из этих других моделей, может быть выражен в лямбда-исчислении, и наоборот. Согласно тезису Чёрча-Тьюринга , обе модели могут выражать любые возможные вычисления.

Возможно, удивительно, что лямбда-исчисление может представить любое мыслимое вычисление, используя только простые понятия абстракции и применения функций, основанные на простой текстовой замене переменных терминами. Но еще более примечательно то, что абстракция даже не требуется. Комбинаторная логика — это модель вычислений, эквивалентная лямбда-исчислению, но без абстракции. Преимущество этого состоит в том, что оценка выражений в лямбда-исчислении довольно сложна, поскольку семантику замены необходимо указывать с большой осторожностью, чтобы избежать проблем с захватом переменных. Напротив, вычисление выражений в комбинаторной логике намного проще, поскольку здесь нет понятия подстановки.

Комбинаторное исчисление

Поскольку абстракция — единственный способ создания функций в лямбда-исчислении, в комбинаторном исчислении ее должно что-то заменить. Вместо абстракции комбинаторное исчисление предоставляет ограниченный набор примитивных функций, из которых могут быть построены другие функции.

Комбинационные термины

Комбинированный термин имеет одну из следующих форм:

Примитивные функции — это комбинаторы или функции, которые, если рассматривать их как лямбда-термины, не содержат свободных переменных .

Чтобы сократить обозначения, принято считать, что , или даже , обозначает термин . Это то же общее соглашение (левая ассоциативность), что и для многократного применения в лямбда-исчислении. ${\displaystyle (E_{1}E_{2}E_{3}...E_{n})}$ ${\displaystyle E_{1}E_{2}E_{3}...E_{n}}$ ${\displaystyle (...((E_{1}E_{2})E_{3})...E_{n})}$

Редукция комбинаторной логики

В комбинаторной логике каждый примитивный комбинатор имеет правило редукции вида

( п Икс ₁ ... Икс _п ) знак равно E

где E — термин, упоминающий только переменные из набора { x ₁ ... x _n } . Именно таким образом примитивные комбинаторы ведут себя как функции.

Примеры комбинаторов

Простейшим примером комбинатора является I , тождественный комбинатор, определяемый формулой

( я х ) = х

для всех условий x . Другой простой комбинатор — K , который создает постоянные функции: ( K x ) — это функция, которая для любого аргумента возвращает x , поэтому мы говорим

(( K Икс ) y ) знак равно Икс

для всех условий x и y . Или, следуя соглашению о многократном применении,

( К Икс у ) знак равно Икс

Третий комбинатор — S , который представляет собой обобщенную версию приложения:

( S Икс yz ) знак равно ( xz ( yz ))

S применяет x к y после первой подстановки z в каждый из них. Или, другими словами, x применяется к y внутри среды z .

Учитывая S и K , сам I не нужен, так как его можно построить из двух других:

(( СКК ) x )

= ( СКК х )

знак равно ( К Икс ( К Икс ))

= х

для любого термина x . Обратите внимание, что хотя (( SKK ) x ) = ( I x ) для любого x , ( SKK ) сам по себе не равен I. Мы говорим, что термины экстенсионально равны . Расширенное равенство отражает математическое понятие равенства функций: две функции равны, если они всегда дают одинаковые результаты для одних и тех же аргументов. Напротив, сами термины вместе с сокращением примитивных комбинаторов отражают идею интенсионального равенства функций: две функции равны , только если они имеют идентичные реализации вплоть до расширения примитивных комбинаторов. Существует много способов реализовать функцию идентификации; ( СКК ) и я в числе этих способов. ( СКС ) — еще один. Мы будем использовать слово эквивалент для обозначения экстенсионального равенства, оставляя равным для идентичных комбинаторных терминов.

Более интересный комбинатор — комбинатор с фиксированной точкой или Y- комбинатор, который можно использовать для реализации рекурсии .

Полнота базы СК

S и K можно составить так, чтобы получить комбинаторы, которые экстенсионально равны любому лямбда-терму и, следовательно, по тезису Чёрча, любой вычислимой функции. Доказательство состоит в том, чтобы представить преобразование T [ ], которое преобразует произвольный лямбда-терм в эквивалентный комбинатор.

T [ ] можно определить следующим образом:

1. Т [ х ] => х
2. Т [( Е ₁ Е ₂)] => ( Т [ Е ₁] Т [ Е ₂])
3. Т [ λx . E ] => ( K T [ E ]) (если x не встречается свободно в E )
4. Т [ λx . х ] => я
5. Т [ λx . λy . E ] => Т [ λx . Т [ λy . E ]] (если x встречается свободно в E )
6. T [ λx .( E ₁ E ₂)] => ( S T [ λx . E ₁] T [ λx . E₂ ]) (если x встречается свободно в E ₁ или E ₂)

Обратите внимание, что T [ ] в заданном виде не является правильно типизированной математической функцией, а скорее переписчиком терминов: хотя в конечном итоге оно дает комбинатор, преобразование может генерировать промежуточные выражения, которые не являются ни лямбда-термами, ни комбинаторами, согласно правилу (5).

Этот процесс также известен как устранение абстракции . Это определение является исчерпывающим: любое лямбда-выражение будет подчиняться ровно одному из этих правил (см. Краткое описание лямбда-исчисления выше).

Это связано с процессом абстракции скобок , который берет выражение E , построенное на основе переменных и приложения, и создает выражение-комбинатор [x]E, в котором переменная x не является свободной, так что выполняется [ x ] E x = E. Очень простой алгоритм абстракции скобок определяется индукцией по структуре выражений следующим образом: ^[6]

1. [ x ] y  := K y
2. [ х ] х  := я
3. [ Икс ]( Е₁ Е₂ ) = S ([ Икс ] Е₁ )([ Икс ] Е₂ )

Абстракция скобок вызывает перевод лямбда-терминов в выражения комбинатора путем интерпретации лямбда-абстракций с использованием алгоритма абстракции скобок.

Преобразование лямбда-терма в эквивалентный комбинаторный термин

Например, мы преобразуем лямбда-терм λx . λy .( y x ) в комбинаторный термин:

Т [ λx . λy .( y x )]

знак равно Т [ λx . T [ λy .( y x )]] (на 5)

= T [ λx .( S T [ λy . y ] T [ λy . x ])] (на 6)

= T [ λx .( SI T [ λy . x ])] (на 4)

= T [ λx .( SI ( K T [ x ]))] (на 3)

= T [ λx .( SI ( K x ))] (на 1)

= ( S T [ λx .( SI )] T [ λx .( K x )]) (на 6)

= ( S ( K ( SI )) T [ λx .( K x )]) (на 3)

= ( S ( K ( SI )) ( S T [ λx . K ] T [ λx . x ])) (на 6)

= ( S ( K ( SI )) ( S ( KK ) T [ λx . x ])) (на 3)

= ( S ( K ( SI )) ( S ( KK ) I )) (на 4)

Если мы применим этот комбинаторный термин к любым двум терминам x и y (подавая их в виде очереди в комбинатор «справа»), он уменьшится следующим образом:

( S ( K ( S I )) ( S ( K K ) I ) xy)

= ( K ( S I ) x ( S ( K K ) I x) y)

= ( S I ( S ( K K ) I x) y)

знак равно ( я y ( S ( K K ) я ху))

= (y ( S ( K K ) I xy))

= (y ( K K x ( I x) y))

= (y ( K ( I x) y))

= (у ( я х))

= (ух)

Комбинаторное представление ( S ( K ( SI )) ( S ( KK ) I )) намного длиннее, чем представление в виде лямбда-терма λx . λy .(yx). Это типично. В общем, конструкция T [ ] может расширить лямбда-член длины n до комбинаторного члена длины Θ ( n ³ ). ^[7]

Объяснение преобразования T [ ]

Преобразование T [ ] мотивировано желанием устранить абстракцию. Два особых случая, правила 3 ​​и 4, тривиальны: λx . x явно эквивалентен I и λx . Очевидно, что E эквивалентно ( K T [ E ]), если x не появляется свободным в E.

Первые два правила также просты: переменные преобразуются сами в себя, а приложения, которые разрешены в комбинаторных терминах, преобразуются в комбинаторы простым преобразованием приложения и аргумента в комбинаторы.

Интерес представляют правила 5 и 6. Правило 5 просто гласит, что для преобразования сложной абстракции в комбинатор мы должны сначала преобразовать ее тело в комбинатор, а затем устранить абстракцию. Правило 6 фактически устраняет абстракцию.

λx .( E ₁ E ₂) — это функция, которая принимает аргумент, скажем a , и подставляет его в лямбда-термин ( E ₁ E ₂) вместо x , получая ( E ₁ E ₂)[ x  : = a ] . Но подставить a в ( E ₁ E ₂) вместо x — это то же самое, что подставить его одновременно в E ₁ и E ₂, поэтому

( E ₁ E ₂)[ x  := a ] = ( E ₁[ x  := a ] E ₂[ x  := a ])

( λx .( E ₁ E ₂) а ) знак равно (( λx . E ₁ а ) ( λx . E ₂ а ))

знак равно ( S λx . E ₁ λx . E ₂ а )

знак равно (( S λx . E₁ λx . E ₂) а )

По экстенсиональному равенству

λx .( E ₁ E ₂) = ( S λx . E ₁ λx . E ₂)

Следовательно, чтобы найти комбинатор, эквивалентный λx .( E ₁ E ₂), достаточно найти комбинатор, эквивалентный ( S λx . E ₁ λx . E ₂), и

( S Т [ λx . E ₁] T [ λx . E ₂])

очевидно, отвечает всем требованиям. E ₁ и E ₂ содержат строго меньше приложений, чем ( E ₁ E ₂), поэтому рекурсия должна завершиться лямбда-термом вообще без приложений — либо переменной, либо термином формы λx . Э. _

Упрощения трансформации

η-редукция

Комбинаторы, порожденные преобразованием T [ ], можно уменьшить, если принять во внимание правило η-редукции :

T [ λx .( E x )] = T [ E ] (если x не свободен в E )

λx .( E x) — функция, которая принимает аргумент x и применяет к нему функцию E ; это экстенсионально равно самой функции E. Поэтому достаточно преобразовать E к комбинаторной форме.

Принимая во внимание это упрощение, приведенный выше пример выглядит следующим образом:

  Т [ λx . λy .( y x )]

"="

= ( S ( K ( SI )) T [ λx .( K x )])

= ( S ( K ( SI )) K ) (путем η-редукции)

Этот комбинатор эквивалентен предыдущему, более длинному:

  ( S ( K ( SI )) K x y )

знак равно ( K ( SI ) Икс ( K Икс ) y )

знак равно ( SI ( K Икс ) y )

знак равно ( я y ( K x y ))

знак равно ( у ( К Икс у ))

= ( ух )

Аналогично, исходная версия преобразования T [ ] преобразовала тождественную функцию λf . λx .( f x ) в ( S ( S ( KS ) ( S ( KK ) I )) ( KI )). По правилу η-редукции λf . λx .( f x ) преобразуется в I .

Однобалльная основа

Существуют одноточечные базы, из которых можно составить каждый комбинатор, экстенсионально равный любому лямбда-терму. Простейшим примером такого базиса является { X }, где:

Икс ≡ λx .((x S ) K )

Нетрудно убедиться в том, что:

Икс ( Икс ( Х Х )) = ^β K и

Икс ( Икс ( Икс ( Икс Икс ))) знак равно ^β S .

Поскольку { K , S } является базисом, отсюда следует, что { X } тоже является базисом. Язык программирования Iota использует X в качестве единственного комбинатора.

Другой простой пример одноточечного базиса:

X' ≡ λx .(x K S K ) с

( X' X' ) X' = ^β K и

Икс' ( Х' Х' ) = ^β S

На самом деле таких баз существует бесконечно много. ^[8]

Комбинаторы Б, С

В дополнение к S и K Шенфинкель (1924) включил два комбинатора, которые теперь называются B и C , со следующими сокращениями:

( C ж г Икс ) знак равно (( ж Икс ) г )

( B ж г Икс ) знак равно ( ж ( г Икс ))

Он также объясняет, как их, в свою очередь, можно выразить, используя только S и K :

B знак равно ( S ( KS ) K )

C знак равно ( S ( S ( K ( S ( KS ) K )) S ) ( KK ))

Эти комбинаторы чрезвычайно полезны при переводе логики предикатов или лямбда-исчисления в выражения комбинатора. Их также использовал Карри , а намного позже Дэвид Тернер , чье имя было связано с их вычислительным использованием. Используя их, мы можем расширить правила преобразования следующим образом:

1. Т [ х ] ⇒ х
2. Т [( E₁ E₂ )] ⇒ ( Т [ E₁ ] Т [ E₂ ])
3. Т [ λx . E ] ⇒ ( K T [ E ]) (если x не свободен в E )
4. Т [ λx . х ] ⇒ Я
5. Т [ λx . λy . Е ] ⇒ Т [ λx . Т [ λy . E ]] (если x свободен в E )
6. T [ λx .( E₁ E₂ )] ⇒ ( S T [ λx . E₁ ] T [ λx . E₂ ]) (если x свободен как в E₁, так и в E₂ )
7. T [ λx .( E₁ E₂ )] ⇒ ( C T [ λx . E₁ ] T [ E₂ ]) (если x свободен в E₁ , но не E₂ )
8. T [ λx .( E₁ E₂ )] ⇒ ( BT [ E₁ ] T [ λx . E₂ ]) (если x свободен в E₂ , но не в E₁ )

Используя комбинаторы B и C , преобразование λx . λy .( y x ) выглядит так:

  Т [ λx . λy .( y x )]

знак равно Т [ λx . Т [ λy .( y x )]]

= T [ λx .( C T [ λy . y ] x )] (по правилу 7)

знак равно Т [ λx .( C I x )]

= ( C I ) (η-редукция)

= (традиционные канонические обозначения: ) ${\displaystyle \mathbf {C} _{*}}$ ${\displaystyle \mathbf {X} _{*}=\mathbf {XI} }$

= (традиционные канонические обозначения: ) ${\displaystyle \mathbf {I} '}$ ${\displaystyle \mathbf {X} '=\mathbf {CX} }$

И действительно, ( C I x y ) сводится к ( y x ):

  ( С я х у )

= ( я y x )

= ( у Икс )

Мотивация здесь в том, что B и C являются ограниченными версиями S. В то время как S принимает значение и подставляет его как в приложение, так и в его аргумент перед выполнением приложения, C выполняет замену только в приложении, а B только в аргументе.

Современные названия комбинаторов взяты из докторской диссертации Хаскелла Карри 1930 года (см. Система B, C, K, W ). В оригинальной статье Шенфинкеля то, что мы сейчас называем S , K , I , B и C , называлось S , C , I , Z и T соответственно.

Уменьшение размера комбинатора в результате новых правил преобразования также может быть достигнуто без введения B и C , как показано в разделе 3.2 Тромпа (2008).

Расчет CL _K и CL _I

Необходимо проводить различие между исчислением CL _K , описанным в этой статье, и исчислением CL _I. Это различие соответствует разнице между исчислением λ _K и λ _I. В отличие от исчисления λ _K , исчисление λ _I ограничивает абстракции:

λx . E , где x имеет хотя бы одно свободное вхождение в E.

Как следствие, комбинатор K отсутствует ни в исчислении λ _I , ни в исчислении CL _I. Константы CL _I : I , B , C и S , которые образуют основу, из которой могут быть составлены все термины CL _I (равенство по модулю). Каждый терм λ _I может быть преобразован в равный комбинатор CL _I по правилам, аналогичным представленным выше для преобразования термов λ _K в комбинаторы CL _K. См. главу 9 в Barendregt (1984).

Обратное преобразование

Преобразование L [ ] из комбинаторных термов в лямбда-термины тривиально:

L [ я ] знак равно λx . Икс

L [ K ] знак равно λx . λy . Икс

L [ C ] знак равно λx . λy . λz .( Икс z y )

L [ B ] знак равно λx . λy . λz .( Икс ( y z ))

L [ S ] знак равно λx . λy . λz .( Икс z ( y z ))

L [( E₁ E₂ )] = ( L [ E₁ ] L [ E₂ ])

Однако обратите внимание, что это преобразование не является обратным преобразованием ни одной из версий T [ ], которые мы видели.

Неразрешимость комбинаторного исчисления

Нормальная форма — это любой комбинаторный термин, в котором встречающиеся примитивные комбинаторы, если таковые имеются, не применяются к достаточному количеству аргументов для упрощения. Неизвестно, имеет ли общий комбинаторный термин нормальную форму; эквивалентны ли два комбинаторных термина и т. д. Это можно показать так же, как и для соответствующих задач для лямбда-термов.

Комбинаторно-логический аналог теоремы Райса гласит, что не существует полного нетривиального предиката. Предикат — это комбинатор , который при применении возвращает либо T , либо F (где T и F представляют собой общепринятые кодировки Чёрча истинного и ложного, λx . λy . x и λx . λy . y , преобразованные в комбинаторную логику; его комбинаторные версии имеют T = K и F = ( K I ) ). Предикат N является нетривиальным, если существуют два аргумента A и B такие, что NA = T и N B = F . Комбинатор N является полным , если N M имеет нормальную форму для каждого аргумента M . Тогда аналог теоремы Райса гласит, что каждый полный предикат тривиален. Доказательство этой теоремы довольно простое.

Доказательство

Доведением до абсурда. Предположим , существует полный нетривиальный предикат, скажем N. Поскольку предполагается, что N нетривиально, существуют комбинаторы A и B такие, что

( N А ) = Т и

( N B ) знак равно F .

Определим ОТРИЦАНИЕ ≡ λx .(если ( N x ), то B else A ) ≡ λx .(( N x ) B A )

Определите АБСУРДУМ ≡ ( Y ОТРИЦАНИЕ)

Теорема о неподвижной точке дает: АБСУРДУМ = (ОТРИЦАНИЕ АБСУРДУМ), для

АБСУРДУМ ≡ ( ОТРИЦАНИЕ Y ) = (ОТРИЦАНИЕ ( ОТРИЦАНИЕ Y )) ≡ (ОТРИЦАНИЕ АБСУРДУМ).

Поскольку N должно быть полным либо:

1. ( N ABSURDUM) = F или
2. ( Н АБСУРДУМ) = Т

• Случай 1: F = ( N АБСУРДУМ) = N (ОТРИЦАНИЕ АБСУРДУМ ) = ( NA ) = T , противоречие.
• Случай 2: T = ( N АБСУРДУМ) = N (ОТРИЦАНИЕ АБСУРДУМ) = ( N B ) = F , снова противоречие.

Следовательно, ( N ABSURDUM) не является ни T , ни F , что противоречит предположению, что N будет полным нетривиальным предикатом. КЭД

Из этой теоремы о неопределимости сразу следует, что не существует полного предиката, который мог бы различать термины, имеющие нормальную форму, и термины, не имеющие нормальной формы. Отсюда также следует, что не существует полного предиката, скажем EQUAL, такого, что:

(РАВНО AB ) = T , если A = B и

(РАВНО AB ) = F , если А ≠ B .

Если бы EQUAL существовало, то для всех A λx . (EQUAL x A ) должен быть полным нетривиальным предикатом.

Приложения

Компиляция функциональных языков

Дэвид Тернер использовал свои комбинаторы для реализации языка программирования SASL .

Кеннет Э. Айверсон использовал примитивы, основанные на комбинаторах Карри, в своем языке программирования J , преемнике APL . Это позволило сделать то, что Айверсон назвал неявным программированием , то есть программирование в функциональных выражениях, не содержащих переменных, а также мощные инструменты для работы с такими программами. Оказывается, неявное программирование возможно на любом APL-подобном языке с определяемыми пользователем операторами. ^[9]

Логика

Изоморфизм Карри–Ховарда подразумевает связь между логикой и программированием: каждое доказательство теоремы интуиционистской логики соответствует редукции типизированного лямбда-терма, и наоборот. Более того, теоремы можно идентифицировать по сигнатурам функционального типа. В частности, типизированная комбинаторная логика соответствует системе Гильберта в теории доказательств .

Комбинаторы K и S соответствуют аксиомам

АК : А → ( Б → А ),

КАК : ( А → ( В → С )) → (( А → В ) → ( А → С )),

и применение функции соответствует правилу отделения (modus ponens)

МП : из А и А → Б выводится Б.

Исчисление, состоящее из AK , AS и MP , является полным для импликативного фрагмента интуиционистской логики, что можно увидеть следующим образом. Рассмотрим множество W всех дедуктивно замкнутых множеств формул, упорядоченных по включению . Тогда – интуиционистский фрейм Крипке , и мы определяем модель в этом фрейме формулой ${\displaystyle \langle W,\subseteq \rangle }$ ${\displaystyle \Vdash }$

${\displaystyle X\Vdash A\iff A\in X.}$

Это определение подчиняется условиям выполнения →: с одной стороны, если , и таковы, что и , то по modus ponens. С другой стороны, если , то по теореме о дедукции , таким образом, дедуктивное замыкание - это такой элемент , что , , и . ${\displaystyle X\Vdash A\to B}$ ${\displaystyle Y\in W}$ ${\displaystyle Y\supseteq X}$ ${\displaystyle Y\Vdash A}$ ${\displaystyle Y\Vdash B}$ ${\displaystyle X\not \Vdash A\to B}$ ${\displaystyle X,A\not \vdash B}$ ${\displaystyle X\cup \{A\}}$ ${\displaystyle Y\in W}$ ${\displaystyle Y\supseteq X}$ ${\displaystyle Y\Vdash A}$ ${\displaystyle Y\not \Vdash B}$

Пусть А — любая формула, недоказуемая в исчислении. Тогда A не принадлежит дедуктивному замыканию X пустого множества, таким образом , и A не является интуиционистски допустимым. ${\displaystyle X\not \Vdash A}$

Смотрите также

• Прикладные вычислительные системы
• Система B, C, K, W
• Категориальная абстрактная машина
• Комбинаторная категориальная грамматика
• Явная замена
• Комбинатор с фиксированной точкой
• Машина сокращения графа
• Лямбда-исчисление и цилиндрическая алгебра , другие подходы к моделированию количественной оценки и исключению переменных
• Комбинаторный расчет SKI
• Суперкомбинатор
• Посмеяться над пересмешником

Рекомендации

1. Шёнфинкель 1924, Статья, основавшая комбинаторную логику. Английский перевод: Шенфинкель (1967).
2. Карри 1930.
3. Селдин 2008.
4. Барендрегт 1984.
5. Хиндли и Мередит 1990.
6. Тернер 1979.
7. Лачовский 2018.
8. Гольдберг 2004.
9. Черлин 1991.

Литература

• Барендрегт, Хендрик Питер (1984). Лямбда-исчисление, его синтаксис и семантика. Исследования по логике и основам математики . Том. 103. Северная Голландия . ISBN 0-444-87508-5.
• Черлин, Эдвард (1991). «Чистые функции в APL и J». Материалы международной конференции по APL'91-APL'91 . стр. 88–93. дои : 10.1145/114054.114065. ISBN 0897914414. S2CID  25802202.
• Карри, Хаскелл Брукс (1930). «Grundlagen der Kombinatorischen Logik» [Основы комбинаторной логики]. Американский журнал математики (на немецком языке). Издательство Университета Джонса Хопкинса. 52 (3): 509–536. дои : 10.2307/2370619. JSTOR  2370619.
• Карри, Хаскелл Брукс ; Фейс, Роберт (1958). Комбинаторная логика . Том. I. Амстердам: Северная Голландия. ISBN 0-7204-2208-6.
• Карри, Хаскелл Брукс ; Хиндли, Дж. Роджер ; Селдин, Джонатан П. (1972). Комбинаторная логика . Том. II. Амстердам: Северная Голландия. ISBN 0-7204-2208-6.
• Филд, Энтони Дж.; Харрисон, Питер Г. (1998). Функциональное программирование . Аддисон-Уэсли. ISBN 0-201-19249-7.
• Гольдберг, Майер (2004). «Построение одноточечных базисов в расширенных лямбда-исчислениях». Письма об обработке информации . 89 (6): 281–286. дои : 10.1016/j.ipl.2003.12.005.
• Хиндли, Дж. Роджер ; Мередит, Дэвид (1990). «Основные типовые схемы и сокращенное отрядение». Журнал символической логики . 55 (1): 90–105. дои : 10.2307/2274956. JSTOR  2274956. MR  1043546. S2CID  6930576.
• Хиндли, Дж. Роджер ; Селдин, Джонатан П. (2008) [1986]. Лямбда-исчисление и комбинаторы: Введение (2-е изд.). Издательство Кембриджского университета . ISBN 9780521898850.
• Лаховский, Лукаш (2018). «О сложности стандартного перевода лямбда-исчисления в комбинаторную логику». Доклады по математической логике . 2018 (53): 19–42. дои : 10.4467/20842589RM.18.002.8835 . Проверено 9 сентября 2018 г.
• Полсон, Лоуренс К. (1995). Основы функционального программирования. Кембриджский университет.
• Куайн, Уиллард Ван Орман (1960). «Переменные объяснены». Труды Американского философского общества . 104 (3): 343–347. JSTOR  985250. Перепечатано как глава 23 Quine (1996).
• Куайн, Уиллард Ван Орман (1996) [1960]. «Переменные объяснены». Избранные статьи по логике (Enl. Ed., 2. Печатное издание). Кембридж, Массачусетс: Издательство Гарвардского университета . стр. 227–235. ISBN 9780674798373.
• Шенфинкель, Моисей (1924). «Über die Bausteine ​​der Mathematischen Logik» (PDF) . Mathematische Annalen (на немецком языке). 92 (3–4): 305–316. дои : 10.1007/bf01448013. S2CID  118507515. Статья, основавшая комбинаторную логику. Английский перевод: Шёнфинкель (1967)
• Шенфинкель, Моисей (1967) [1924]. Ван Хейеноорт, Жан (ред.). Über die Bausteine ​​der mathematischen Logik [ О строительных блоках математической логики ]. От Фреге до Гёделя: справочник по математической логике, 1879–1931. Перевод Бауэра-Менгельберга, Стефана. Кембридж, Массачусетс, США: Издательство Гарвардского университета . стр. 355–366. ISBN 978-0674324497. OCLC  503886453.
• Селдин, Джонатан П. (3 марта 2008 г.). «Логика Карри и Черча» (PDF) . Проверено 17 сентября 2023 г.
• Смалльян, Раймонд (1985). Посмеяться над пересмешником и другими логическими головоломками, включая удивительное приключение в области комбинаторной логики . Кнопф. ISBN 0-394-53491-3. Нежное введение в комбинаторную логику, представленное в виде серии развлекательных головоломок с использованием метафор наблюдения за птицами.
• Смуллян, Раймонд (1994). Диагонализация и самореференция . Оксфордские руководства по логике. Том. 27. Оксфорд и Нью-Йорк: Издательство Оксфордского университета . ISBN 978-0198534501. Главы 17–20 представляют собой более формальное введение в комбинаторную логику с особым упором на результаты с фиксированной точкой.
• Соренсен, Мортен Хейне Б; Уржичин, Павел (2006) [1999]. Лекции по изоморфизму Карри – Говарда (PDF) . Исследования по логике и основам математики. Том. 149 (1-е изд.). Эльзевир . п. 442. ИСБН 978-0444520777. Архивировано из оригинала (PDF) 16 октября 2005 г. Проверено 22 апреля 2017 г.
• Тромп, Джон (2008). «Двоичное лямбда-исчисление и комбинаторная логика» (PDF) . В Калуде, Кристиан С. (ред.). Случайность и сложность: от Лейбница до Хайтина . Мировое научное издательство. Архивировано из оригинала (PDF) 4 марта 2016 г.
• Тернер, Дэвид А. (1979). «Другой алгоритм абстракции скобок». Журнал символической логики . 44 (2): 267–270. дои : 10.2307/2273733. JSTOR  2273733. S2CID  35835482.
• Вольфенгаген, ВЕ (2003). Комбинаторная логика в программировании: Вычисления с объектами на примерах и упражнениях (2-е изд.). Москва: ISBN ООО «Центр ЮрИнфоР». 5-89158-101-9.
• Вольфрам, Стивен (2021). Комбинаторы: взгляд на столетие. Вольфрам Медиа . ISBN 978-1-57955-043-1. Празднование развития комбинаторов спустя сто лет после того, как их представил Шенфинкель (1924 г.).(электронная книга: ISBN 978-1-57955-044-8 ) 

Внешние ссылки

• Стэнфордская энциклопедия философии : «Комбинаторная логика» Каталин Бимбо .
• 1920–1931 Блокноты Карри.
• Кинан, Дэвид К. (2001) «Препарировать пересмешника: графическое обозначение лямбда-исчисления с анимированной редукцией».
• Ратман, Крис, «Птицы-комбинаторы». Таблица, отражающая большую часть сути Смалляна (1985).
• Комбинаторы перетаскивания. (Java-апплет)
• Бинарное лямбда-исчисление и комбинаторная логика.
• Веб-сервер комбинационной логической редукции
• Вольфрам, Стивен (29 апреля 2020 г.). Комбинаторы: 100-летие. Проект Wolfram Physics на YouTube . Проверено 26 сентября 2023 г.