Бинарная комбинаторная логика
-
Определение и основы BCL
- Двоичная комбинаторная логика использует двоичные символы для формулирования комбинаторной логики.
- Комбинаторы S и K позволяют создавать сложные булевы функции.
-
Применение в теории сложности
- BCL используется для определения колмогоровской сложности программ.
-
Синтаксис и семантика
- BCL использует синтаксис Бэкуса-Наура для описания логических функций.
- Семантика BCL основана на денотационной семантике с определенными правилами для комбинаторов K и S.
-
Операционная семантика
- Операционная семантика BCL включает правила перезаписи для упрощения выражений.
-
Полнота по Тьюрингу
- BCL является полным по Тьюрингу и может использоваться для репликации алгоритмов, таких как машины Тьюринга и клеточные автоматы.
-
Дополнительные ресурсы
- Ссылки на игровую площадку Джона по лямбда-исчислению и комбинаторной логике, а также на минимальную реализацию на C.
Полный текст статьи: