Комбинаторы — это просто!: различия между версиями

Содержимое удалено Содержимое добавлено
м Вставлены пробелы, некоторые пробелы заменены на неразрывные
Строка 1:
:''Исходный вариант статьи (Р. В. Душкин, «Комбинаторы? - Это просто!») опубликован в [[Журнал «Потенциал»|журнале «Потенциал»]], №7№ 7, 2006.''
 
Данная статья описывает основы комбинаторной логики - математической науки о вычислениях, в которой любые объекты изучения выражаются при помощи двух базовых объектов S и K, называемых комбинаторами, и одной операции над ними - операции применения одного комбинатора к другому.
Строка 6:
 
 
Комбинаторная логика (от слова «комбинатор», а не «комбинаторика») — это направление в математической логике, разработанное в первой половине XX века логиками Мозесом Шёнфинкелем и Хаскеллом Карри в качестве науки о вычислительных процессах. Хотя первоначально этот вид логики претендовал только на то, чтобы удалить из логических высказываний переменные, через некоторое время в информатике были получены прикладные результаты, показавшие, что комбинаторную логику можно использовать для проведения вычислений.
 
На комбинаторную логику можно смотреть как на некоторое упрощение
Строка 13:
ограниченным набором символов, называемых «комбинаторами». Такие
комбинаторы не содержат переменных, являются функциями высшего
порядка, т. е. в качестве аргументов могут принимать на вход другие
функции, а также описывают определённые правила преобразования
объектов, поданных им на вход в качестве аргументов.
Строка 56:
Комбинаторные термы (или просто «выражения») будут обозначаться
заглавными буквами латинского алфавита, возможно также с индексами:
<math>M</math>, <math>N</math> и т. &nbsp;д.
 
Из специальных символов в комбинаторной логике используется всего
Строка 116:
является тем набором первоначальных комбинаторов, через который
выражаются все прочие комбинаторы. Однако это не минимальный базис,
ибо наличие комбинатора '''I''' не обязательно в нём, т. &nbsp;к.
его можно выразить через комбинаторы '''S''' и '''K''':
 
Строка 157:
Как видно, первые три правила являются описанием свойств
рефлексивности, симметричности и транзитивности. Набор этих свойств
являет собой характеристики отношения эквивалентности, т. &nbsp;е.
отношение конвертируемости (<math>=</math>) делит всё множество комбинаторных
термов на некоторые классы эквивалентности, относительно которых
Строка 232:
 
Здесь видно, что первая альтернатива не подходит автоматически,
т. &nbsp;к. канцелятор '''K''' отменяет переменную <math>x</math>, которая
должна появиться в самом конце. Соответственно далее надо
рассматривать только вторую альтернативу и искать способ выражения
Строка 246:
'''S'''. Поэтому вторую альтернативу можно не рассматривать,
а вернуться только к первой. В ней остаётся неизвестный объект <math>2</math>,
который не участвует в цепочке вывода, т. &nbsp;к. уничтожается
канцелятором. Поэтому вместо него может стоять любой комбинатор,
например, всё тот же '''K'''. Так и получается, что выражение
Строка 255:
Этот пример также показал, что способов разложения объектов в
комбинаторном базисе существует бесконечное множество, поэтому
всегда имеет смысл говорить о «минимальном» разложении, т. &nbsp;е.
таком, в записи которого используется минимальное число комбинаторов
и скобок.
Строка 423:
и проводить вычисления над закодированными данными более эффективно.
Однако этот способ кодирования данных является довольно интересным с
точки зрения математики, т. &nbsp;к. позволяет понять, в том числе, и то,
что данные могут нести внутри себя и способы их обработки.
 
Строка 446:
вообще не является необходимым &mdash; можно вполне обойтись и без него.
Сами по себе значения истинности являются условными выражениями,
т. &nbsp;к. возвращают первый или второй операнд в зависимости от своей
природы. Поэтому комбинатор '''if''' является тождеством для
трёх операндов, первый из которых должен быть значением истинности.
Строка 494:
<math>(SB)^{3}(KI) =SB(SB(SB))(KI)</math>
 
и т. &nbsp;д. Т. &nbsp;е. по индукции эти объекты можно определить как:
 
 
Строка 539:
Данный комбинатор составляет пару из двух заданных объектов любой
природы. Для того, чтобы достать эти объекты из пары, необходимы
т. &nbsp;н. «селекторы», т. &nbsp;е. функции для доступа к элементам пары.
Эти селекторы можно определить так: