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