Институт №8 МАИ

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

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

Ключевые существенные понятия в КЛ - это объектные способы их комбинирования.

Комбинирование выполняется посредством выделенных под это объектов-констант, называемых комбинаторами.

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

• логику высказываний, логику предикатов, арифметические системы и ряд других.

---

Комбинаторная логика стала одним из основных математических аппаратов в Computer Science. На начальном этапе предполагается наличие всего трёх объектов-комбинаторов, пользуясь исключительно которыми, можно построить богатые системы программирования.

Комбинаторная логика вместе с лямбда-исчислением признаётся основой для рассуждений в терминах объектов.

• Колмогоровская сложность объекта - мера вычислительных ресурсов, необходимых для точного определения этого объекта.
• Она известна как описательная сложность, алгоритмическая энтропия или алгоритмическая сложность. Названа в честь советсткого математика Андрея Колмогорова.
• Андрей Колмогоров участвовал в создании теории вероятности (!), топологии, интуитивной логики, классической механики, алгоритмической информационной теории (!) и др.

Суть колмогоровской сложности

• Сложность строки - это длина описания этой строки на некотором универсальном языке описания.
• Строки, чья колмогоровская сложность слабо зависит от размера, не являются сложными.

  • Т.е. строку “привет, как дела?” проще описать, чем строку той же длины, но состояющую из бессмысленного набора букв “прваолрпдвапол”, и даже если она будет короче.

• Чувство сложности описания относится также и к выбору языка, описывающего сложность.
• В частности, для этого используют языки Lisp, Pascal, Java.

Сложность даже не зависит от описываемого объекта.

Какой язык считается идеальным для описания сложности?

• Первая часть описания описывает другой описательный язык.
• Вторая часть описания есть описание объекта на этом языке.

  Если быть точным, первая часть описания - это компьютерная программа (в частности, компилятор), а вторая часть - вводимый код, который после работы выдаёт объект.

• Анализ составлен на основе статьи Дж. Тромпа от 17 марта 2002г.
• Перейти к ней