Комбинаторы — это просто!: различия между версиями
Содержимое удалено Содержимое добавлено
Vadzimzie (обсуждение | вклад) |
FeelUs (обсуждение | вклад) м убрал рекламные внешние ссылки на все равно не работающие сайты |
||
Строка 1:
:''Исходный вариант статьи (Р. В. Душкин, «Комбинаторы? — Это просто!») опубликован в [[Журнал «Потенциал»|журнале «Потенциал»]], № 7, 2006.''
Данная статья описывает основы [[w:Комбинаторная логика|комбинаторной логики]] — [[w:Математика|математической науки]] о [[w:Вычисление|вычислениях]], в которой любые объекты изучения выражаются при помощи двух базовых объектов <math>S</math> и <math>K</math>, называемых [[w:Комбинатор|комбинаторами]], и одной операции над ними — операции применения одного комбинатора к другому
== Введение ==
Комбинаторная логика (от слова «комбинатор», а не «[[w:Комбинаторика|комбинаторика]]») — это направление в [[w:Математическая логика|математической логике]], разработанное в первой половине XX века логиками [[w:Шейнфинкель, Моисей Исаевич|Моисеем Шейнфинкелем]] и [[w:Карри, Хаскелл|Хаскеллом Карри]] в качестве науки о вычислительных процессах. Хотя первоначально этот вид логики претендовал только на то, чтобы удалить из [[w:Высказывание (логика)|логических высказываний]] переменные, через некоторое время в [[w:Информатика|информатике]] были получены прикладные результаты, показавшие, что комбинаторную логику можно использовать для проведения вычислений
На комбинаторную логику можно смотреть как на некоторое упрощение [[w:Лямбда-исчисление|λ-исчисления]] {{ref|lambda}}, в котором нет символа λ, а все функциональные абстракции представлены ограниченным набором символов, называемых «комбинаторами». Такие комбинаторы не содержат [[w:Переменная|переменных]], являются [[w:Функция высшего порядка|функциями высшего порядка]], то есть в качестве аргументов могут принимать на вход другие [[w:Функция (математика)|функции]], а также описывают определённые правила преобразования
объектов, поданных им на вход в качестве аргументов
Другими словами, комбинаторная логика — это формализм для представления функциональных зависимостей между входными и выходными данными. В этом формализме зависимости и сами данные записываются в одном и том же весьма ограниченном [[w:Алфавит (математика)|алфавите]
== Формальная теория ==
Базовые объекты комбинаторной логики, участвующие в [[w:Формальная теория|формальной системе]], определяют саму комбинаторную логику. Определим следующие элементы формальной системы
# Алфавит.
| |||