Бинарная комбинаторная логика - Binary combinatory logic
 | Эта статья может быть непонятным или очень трудным для понимания. (Июль 2020 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
 | Эта статья предоставляет недостаточный контекст для тех, кто не знаком с предметом. (Июль 2020 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
Бинарная комбинаторная логика (BCL) является формулировкой комбинаторная логика используя только символы 0 и 1.[1] BCL имеет приложения в теории сложности программного размера (Колмогоровская сложность ).[1][2]
Определение
Синтаксис
<срок> ::= 00 | 01 | 1 <срок> <срок>Семантика
В денотационная семантика BCL можно указать следующим образом:
[ 00 ] == K[ 01 ] == S[1] == ([ ] [ ])
куда "[...]"сокращает" значение ...". Здесь K и S являются KS-базисные комбинаторы, и ( ) это заявление операция по комбинаторная логика. (Префикс 1 соответствует левой круглой скобке, правая скобка не нужна для устранения неоднозначности.)
Таким образом, существует четыре эквивалентных формулировки BCL, в зависимости от способа кодирования триплета (K, S, левая скобка). Это (00, 01, 1) (как в настоящей версии), (01, 00, 1), (10, 11, 0), и (11, 10, 0).
В операционная семантика BCL, кроме эта-редукции (которая не требуется для Полнота по Тьюрингу ), может быть очень компактно определено следующим переписывание правила для подтемнов данного термина, разбор слева:
1100кси → х11101xyz → 11xz1yz
куда Икс, у, и z являются произвольными подтермами. (Обратите внимание, например, что, поскольку синтаксический анализ выполняется слева, 10000 не является подтекстом 11010000.)
Смотрите также
Рекомендации
- ^ а б Тромп, Джон (2007), "Бинарное лямбда-исчисление и комбинаторная логика", Случайность и сложность (PDF), World Sci. Publ., Hackensack, NJ, стр. 237–260, CiteSeerX 10.1.1.695.3142, Дои:10.1142/9789812770837_0014, ISBN 978-981-277-082-0, МИСТЕР 2427553.
- ^ Дивайн, Шон (2009), «Понимание алгоритмической энтропии», Энтропия, 11 (1): 85–110, Дои:10.3390 / e11010085, МИСТЕР 2534819