Бинарная комбинаторная логика ( BCL ) — это язык компьютерного программирования , который использует двоичные термины 0 и 1 для создания полной формулировки комбинаторной логики , используя только символы 0 и 1. [1] Используя комбинаторы S и K, можно выполнять сложные функции булевой алгебры. сделал. BCL имеет приложения в теории сложности размера программы ( колмогоровской сложности ). [1] [2]
Используя комбинаторы K и S комбинаторной логики , логические функции можно представить как функции комбинаторов:
< термин > ::= 00 | 01 | 1 < срок > < срок >Денотационная семантика BCL может быть определена следующим образом:
[ 00 ] == K[ 01 ] == S[ 1 <term1> <term2> ] == ( [<term1>] [<term2>] ) где " [...]" сокращает "значение ...". Здесь Kи S– KS -базисные комбинаторы , а ( )– прикладная операция комбинаторной логики . (Префикс 1соответствует левой скобке, правые скобки не нужны для устранения неоднозначности.)
Таким образом, существует четыре эквивалентные формулировки BCL, в зависимости от способа кодирования триплета (K, S, левая скобка). Это (00, 01, 1)(как и в текущей версии), (01, 00, 1), (10, 11, 0)и (11, 10, 0).
Операционная семантика BCL, помимо эта-редукции (которая не требуется для полноты по Тьюрингу ), может быть очень компактно определена с помощью следующих правил перезаписи для подтермов данного термина, анализируя слева:
1100xy → x 11101xyz → 11xz1yz где x, y, и z– произвольные подчлены. (Обратите внимание, например, что, поскольку синтаксический анализ выполняется слева, 10000он не является подтермом 11010000.)
BCL можно использовать для репликации таких алгоритмов, как машины Тьюринга и клеточные автоматы . [3] BCL является полным по Тьюрингу .