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

Не путать с комбинационная логика, тема в цифровой электронике.

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

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

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

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

В вычислениях

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

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

Комбинаторной логике можно дать самые разные интерпретации. Многие ранние работы Карри показали, как преобразовать наборы аксиом традиционной логики в уравнения комбинаторной логики (Hindley and Meredith 1990). Дана Скотт в 1960-х и 1970-х годах показали, как жениться теория моделей комбинаторная логика.

Резюме лямбда-исчисления

Основная статья: Лямбда-исчисление

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

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

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

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

Условия формы ${\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})}$ тогда его нельзя уменьшить, и говорят, что он находится в нормальная форма.

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

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

Условно мы берем ${\displaystyle (abc)}$ как сокращение для ${\displaystyle ((ab)c)}$ (т.е. приложение лево-ассоциативный ).

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

Площадь Икс является ${\displaystyle x*x}$

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

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

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

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

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

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

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

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

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

Синтаксис	имя	Описание
Икс	Переменная	Символ или строка, представляющая комбинаторный термин.
п	Примитивная функция	Один из символов комбинатора я, K, S.
(M N)	заявка	Применение функции к аргументу. M и N - комбинаторные термины.

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

Чтобы сократить обозначения, общее соглашение таково, что ${\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 это термин, в котором упоминаются только переменные из набора {Икс₁ ... Икс_п}. Таким образом, примитивные комбинаторы ведут себя как функции.

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

Самый простой пример комбинатора: я, объединитель идентичностей, определяемый

(я Икс) = Икс

на все сроки Икс.^[6] Другой простой комбинатор - это K, который производит постоянные функции: (K Икс) - функция, которая для любого аргумента возвращает Икс,^[6] так мы говорим

((K Икс) y) = Икс

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

(K Икс y) = Икс

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

(S x y z) = (х г (у г))

S применяется Икс к y после первой замены z в каждого из них.^[6] Или по-другому, Икс применяется к y внутри окружающей среды z.

Данный S и K, я сам по себе не нужен, так как он может быть построен из двух других:^[6]

((S K K) Икс)

= (S K K Икс)

= (K Икс (K Икс))

= Икс

на любой срок Икс. Обратите внимание, что хотя ((S K K)Икс) = (я Икс) для любого Икс, (S K K) сам по себе не равен я. Мы говорим, что условия внешне равный. Экстенсиональное равенство отражает математическое понятие равенства функций: две функции равный если они всегда дают одинаковые результаты для одних и тех же аргументов. Напротив, сами термины вместе с редукцией примитивных комбинаторов охватывают понятиесодержательное равенство функций: две функции равныйтолько если они имеют идентичные реализации, вплоть до расширения примитивных комбинаций, когда они применяются к достаточному количеству аргументов. Есть много способов реализовать функцию идентификации; (S K K) и янаходятся среди этих способов. (S K S) еще один. Мы будем использовать слово эквивалент для обозначения экстенсионального равенства, сохраняя равный для одинаковых комбинаторных членов.

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

Полнота основы С-К

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

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

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

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

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

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

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

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

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

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

Т[λx.λy.(y Икс)]

= Т[λx.Т[λy.(y Икс)]] (на 5)

= Т[λx.(S Т[λy.y] Т[λy.Икс])] (на 6)

= Т[λx.(S I Т[λy.Икс])] (на 4)

= Т[λx.(S I (K Т[Икс]))] (на 3)

= Т[λx.(S I (K Икс))] (на 1)

= (S Т[λx.(S I)] Т[λx.(K Икс)]) (на 6)

= (S (K (S I)) Т[λx.(K Икс)]) (на 3)

= (S (K (S I)) (S Т[λx.K] Т[λx.Икс])) (на 6)

= (S (K (S I)) (S (К К) Т[λx.Икс])) (на 3)

= (S (K (S I)) (S (К К) я)) (на 4)

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

(S (K (S я)) (S (K K) я) х у)

= (K (S я) Икс (S (K K) я х) у)

= (S я (S (K K) я х) у)

= (я у (S (K K) я х у))

= (y (S (K K) я х у))

= (y (K K Икс (я х) у))

= (y (K (я х) у))

= (y (я Икс))

= (у х)

Комбинаторное представление, (S (K (S I)) (S (К К) я)) намного длиннее, чем представление в виде лямбда-члена, λx.λy. (у х). Это типично. В целом Т[] конструкция может увеличить длину лямбдатерм п до комбинаторного члена длиныΘ (п³).^[8]

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

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

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

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

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

(E₁ E₂)[Икс := а] = (E₁[Икс := а] E₂[Икс := а])

(λ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₁] Т[λx.E₂])

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

Упрощения преобразования

η-редукция

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

Т[λx.(E Икс)] = Т[E] (если Икс не бесплатно в E)

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

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

  Т[λx.λy.(y Икс)]

= ...

= (S (K (S I)) Т[λx.(K Икс)])

= (S (K (S I)) K) (по η-редукции)

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

  (S (K (S I)) K х у)

= (K (S I) Икс (K Икс) y)

= (S I (K Икс) y)

= (я y (K х у))

= (y (K х у))

= (у х)

Точно так же исходная версия Т[] преобразование преобразовало функцию идентичности λf.λx.(ж Икс) в (S (S (K S) (S (К К) я)) (K I)). По правилу η-редукции λf.λx.(ж Икс) преобразуется в я.

Одноточечная основа

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

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

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

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

Икс (Икс (Икс (Икс Икс))) =^β S.

Поскольку {K, S} является базисом, отсюда следует, что {Икс} - это тоже основа. В Йота язык программирования использует Икс как его единственный комбинатор.

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

ИКС' ≡ λx.(Икс K S K) с участием

(ИКС' ИКС') ИКС' =^β K и

ИКС' (ИКС' ИКС') =^β S

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

Комбинаторы B, C

В дополнение к S и K, Schönfinkel статья включала два комбинатора, которые теперь называются B и C, со следующими скидками:

(C ж г Икс) = ((ж Икс) г)

(B ж г Икс) = (ж (г Икс))

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

B = (S (K S) K)

C = (S (S (K (S (K S) K)) S) (К К))

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

1. Т[Икс] ⇒ Икс
2. Т[(E₁ E₂)] ⇒ (Т[E₁] Т[E₂])
3. Т[λx.E] ⇒ (K Т[E]) (если Икс не бесплатно в E)
4. Т[λx.Икс] ⇒ я
5. Т[λx.λy.E] ⇒ Т[λx.Т[λy.E]] (если Икс бесплатно в E)
6. Т[λx.(E₁ E₂)] ⇒ (S Т[λx.E₁] Т[λx.E₂]) (если Икс бесплатно в обоих E₁ и E₂)
7. Т[λx.(E₁ E₂)] ⇒ (C Т[λx.E₁] Т[E₂]) (если Икс бесплатно в E₁ но нет E₂)
8. Т[λx.(E₁ E₂)] ⇒ (B Т[E₁] Т[λx.E₂]) (если Икс бесплатно в E₂ но нет E₁)

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

   Т[λx.λy.(y Икс)]

= Т[λx.Т[λy.(y Икс)]]

= Т[λx.(C Т[λy.y] Икс)] (по правилу 7)

= Т[λx.(C я Икс)]

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

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

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

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

   (C я Икс y)

= (я y Икс)

= (y Икс)

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

Современные названия комбинаторов происходят от Хаскелл Карри докторскую диссертацию 1930 г. (см. Система B, C, K, W ). В Schönfinkel оригинальная бумага, которую мы сейчас называем S, K, я, B и C были названы S, C, я, Z, и Т соответственно.

Уменьшение размера комбинатора, являющееся результатом новых правил преобразования, также может быть достигнуто без введения B и C, как показано в разделе 3.2.^[10]

CL_K против CL_я исчисление

Следует проводить различие между CL_K как описано в этой статье и CL_я исчисление. Различие соответствует различию между λ_K а λ_я исчисление. В отличие от λ_K исчисление, λ_я исчисление ограничивает абстракции:

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

Как следствие, комбинатор K отсутствует в λ_я исчисление ни в CL_я исчисление. Константы CL_я находятся: я, B, C и S, составляющие основу, на которой все CL_я члены могут быть составлены (по модулю равенства). Каждые λ_я термин может быть преобразован в равный CL_я комбинатор в соответствии с правилами, аналогичными приведенным выше для преобразования λ_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₂])

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

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

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

Во-первых, термин

Ω = (S я я (S я я))

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

   (S я я (S я я))

= (я (S я я) (я (S я я)))

= (S я я (я (S я я)))

= (S я я (S я я))

и очевидно, что никакой другой порядок сокращения не может сделать это выражение короче.

Теперь предположим N были комбинатором для обнаружения нормальных форм, таких что

${\displaystyle (\mathbf {N} \ x)={\begin{cases}\mathbf {T} ,{\text{ if }}x{\text{ has a normal form}}\\\mathbf {F} ,{\text{ otherwise.}}\end{cases}}}$

(Куда Т и F представляют собой обычные Церковные кодировки истинного и ложного, λx.λy.Икс и λx.λy.y, преобразованная в комбинаторную логику. Комбинаторные версии имеют Т = K и F = (K я).)

Теперь позвольте

Z = (C (C (B N (S я я)) Ω) я)

теперь рассмотрим термин (S я я Z). Есть ли (S я я Z) иметь нормальную форму? Это происходит тогда и только тогда, когда также выполняется следующее:

   (S я я Z)

= (я Z (я Z))

= (Z (я Z))

= (Z Z)

= (C (C (B N (S я я)) Ω) я Z) (значение Z)

= (C (B N (S я я)) Ω Z я)

= (B N (S я я) Z Ω я)

= (N (S я я Z) Ω я)

Теперь нам нужно подать заявку N к (S я я Z).Либо (S я я Z) имеет нормальный вид или нет. Если это делаетимеют нормальный вид, то сказанное сводится к следующему:

   (N (S я я Z) Ω я)

= (K Ω я) (значение N)

= Ω

но Ω делает не имеют нормальный вид, приходим к противоречию. Но если (S я я Z) делает не имеют нормальную форму, сказанное сокращается следующим образом:

   (N (S я я Z) Ω я)

= (K я Ω я) (значение N)

= (я я)

= я

что означает, что нормальная форма (S я я Z) просто яЕще одно противоречие. Следовательно, гипотетический комбинатор нормальной формы Nне может существовать.

Комбинаторно-логический аналог Теорема Райса говорит, что не существует полного нетривиального предиката. А предикат комбинатор, который при применении возвращает либо Т или F. Предикат N является нетривиальный если есть два аргумента А и B такой, что N А = Т и N B = F. Комбинатор N является полный если и только если NM имеет нормальную форму для каждого аргумента M. Тогда аналог теоремы Райса говорит, что каждый полный предикат тривиален. Доказательство этой теоремы довольно просто.

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

(N А) = Т и

(N B) = F.

Определить ОТРИЦАНИЕ ≡ λx.(если (N Икс) тогда B еще А) ≡ λx.((N Икс) B А)

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

Теорема о фиксированной точке дает: АБСУРДУМ = (ОТРИЦАТЕЛЬНЫЙ АБСУРДМ) для

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

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

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

• Случай 1: F = (N АБСУРДУМ) = N (ОТРИЦАТЕЛЬНЫЙ АБСУРДМ) = (N А) = Т, противоречие.
• Случай 2: Т = (N АБСУРДУМ) = N (ОТРИЦАТЕЛЬНЫЙ АБСУРДУМ) = (N B) = F, опять противоречие.

Следовательно (N ABSURDUM) не является ни Т ни F, что противоречит предположению, что N был бы полным нетривиальным предикатом. Q.E.D.

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

(РАВНО А Б) = Т если А = B и

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

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

Приложения

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

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

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

Логика

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

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

АК: А → (B → А),

ТАК КАК: (А → (B → C)) → ((А → B) → (А → C)),

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

Депутат: от А и А → B сделать вывод B.

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

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

Это определение удовлетворяет условиям выполнения →: с одной стороны, если ${\displaystyle X\Vdash A\to B}$, и ${\displaystyle Y\in W}$ таково, что ${\displaystyle Y\supseteq X}$ и ${\displaystyle Y\Vdash A}$, тогда ${\displaystyle Y\Vdash B}$ пользователя modus ponens. С другой стороны, если ${\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}$.

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

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

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

использованная литература

1. Шенфинкель, Моисей (1924). "Über die Bausteine ​​der Mathematischen Logik" (PDF). Mathematische Annalen. 92 (3–4): 305–316. Дои:10.1007 / bf01448013. Перевод Стефана Бауэра-Менгельберга как «О строительных блоках математической логики» в Жан ван Хейеноорт, 1967. Справочник по математической логике, 1879–1931 гг.. Harvard Univ. Пресс: 355–66.
2. Карри, Хаскелл Брукс (1930). "Grundlagen der Kombinatorischen Logik" [Основы комбинаторной логики]. Американский журнал математики (на немецком). Издательство Университета Джона Хопкинса. 52 (3): 509–536. Дои:10.2307/2370619. JSTOR  2370619.
3. Вольфрам, Стивен (2002). Новый вид науки. Wolfram Media, Inc. стр.1121. ISBN  1-57955-008-8.
4. Селдин, Джонатан (2008). «Логика Карри и Черча» (PDF).
5. Барендрегт 1984.
6. Новый вид науки [1]
7. Тернер, Дэвид А. (1979). «Другой алгоритм для абстракции скобок». Журнал символической логики. 44 (2): 267–270. Дои:10.2307/2273733. JSTOR  2273733.
8. Лачовски, Лукаш (2018). «О сложности стандартного перевода лямбда-исчисления в комбинаторную логику». Отчеты по математической логике (53): 19–42. Дои:10.4467 / 20842589РМ.18.002.8835. Получено 9 сентября 2018.
9. Гольдберг, Майер (2004). «Построение одноточечных базисов в расширенных лямбда-исчислениях». Письма об обработке информации. 89 (6): 281–286. Дои:10.1016 / j.ipl.2003.12.005.
10. Тромп, Джон (2008). «Двоичное лямбда-исчисление и комбинаторная логика» (PDF). В Калуде, Кристиан С. (ред.). Случайность и сложность, от Лейбница до Чайтина. Всемирная научная издательская компания. Архивировано из оригинал (PDF) на 2016-03-04.
11. Черлин, Эдвард (1991). «Чистые функции в APL и J». Материалы Международной конференции по APL '91: 88–93. Дои:10.1145/114054.114065. ISBN  0897914414.

дальнейшее чтение

• Барендрегт, Хендрик Питер (1984). Лямбда-исчисление, его синтаксис и семантика. Исследования по логике и основам математики. Том 103. Северная Голландия. ISBN  0-444-87508-5.
• Карри, Хаскелл Б.; Фейс, Роберт (1958). Комбинаторная логика. Vol. I. Амстердам: Северная Голландия. ISBN  0-7204-2208-6.
• Карри, Хаскелл Б.; Хиндли, Дж. Роджер; Селдин, Джонатан П. (1972). Комбинаторная логика. Vol. II. Амстердам: Северная Голландия. ISBN  0-7204-2208-6.
• Филд, Энтони Дж .; Харрисон, Питер Г. (1998). Функциональное программирование. Эддисон-Уэсли. ISBN  0-201-19249-7.
• Хиндли, Дж. Роджер; Мередит, Дэвид (1990), «Принципиальные типовые схемы и конденсированная отрывка», Журнал символической логики, 55 (1): 90–105, Дои:10.2307/2274956, JSTOR  2274956, Г-Н  1043546
• Хиндли, Дж. Р.; Селдин, Дж. П. (2008). λ-исчисление и комбинаторы: введение. Издательство Кембриджского университета.
• Полсон, Лоуренс С. (1995). Основы функционального программирования. Кембриджский университет.
• Куайн, В.В. (1960). «Объяснение переменных». Труды Американского философского общества. 104 (3): 343–347. JSTOR  985250. Перепечатано как глава 23 книги Куайна. Избранные статьи по логике (1966), стр. 227–235
• Шенфинкель, Моисей, 1924, "Über die Bausteine ​​der Mathematischen Logik, "переведено как" О строительных блоках математической логики "в От Фреге до Гёделя: справочник по математической логике, 1879–1931 гг., Жан ван Хейеноорт, изд. Издательство Гарвардского университета, 1967. ISBN  0-674-32449-8. Статья, обосновавшая комбинаторную логику.
• Смуллян, Раймонд, 1985. Издеваться над пересмешником. Кнопф. ISBN  0-394-53491-3. Мягкое введение в комбинаторную логику, представленное в виде серии развлекательных головоломок с использованием метафор наблюдения за птицами.
• --------, 1994. Диагонализация и самооценка. Oxford Univ. Нажмите. Главы 17–20 представляют собой более формальное введение в комбинаторную логику с особым упором на результаты с фиксированной точкой.
• Соренсен, Мортен Хейне Б. и Павел Уржичин, 1999. Лекции об изоморфизме Карри – Ховарда. Копенгагенский и Варшавский университет, 1999 г.
• Вольфенгаген, В. Э. (2003). Комбинаторная логика в программировании: вычисления с объектами на примерах и упражнениях (2-е изд.). Москва: ООО «Центр ЮрИнфоР». ISBN  5-89158-101-9..

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

• Стэнфордская энциклопедия философии: "Комбинаторная логика "Автор: Каталин Бимбо.
• 1920–1931 Блокноты Карри.
• Кинан, Дэвид С. (2001) "Чтобы рассечь пересмешника: графическое представление лямбда-исчисления с анимированной редукцией. "
• Ратман, Крис "Комбинатор Птицы. "Стол, раскрывающий сущность Смулляна (1985).
• Комбинаторы Drag 'n' Drop. (Java-апплет)
• Двоичное лямбда-исчисление и комбинаторная логика.
• Веб-сервер редукции комбинаторной логики