stringtranslate.com

Двоичная комбинаторная логика

Двоичная комбинаторная логика ( BCL ) — это язык программирования , который использует двоичные термины 0 и 1 для создания полной формулировки комбинаторной логики, используя только символы 0 и 1. [1] Используя комбинаторы S и K, можно создавать сложные функции булевой алгебры. BCL имеет приложения в теории сложности размера программы ( сложности Колмогорова ). [1] [2]

Определение

СК Базис

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

Синтаксис

Форма Бэкуса–Наура :

 < термин >  ::= 00 | 01 | 1 < термин >  < термин >

Семантика

Денотационную семантику BCL можно определить следующим образом:

где " [...]" сокращает "значение ...". Здесь Kи Sявляются комбинаторами KS -базиса , а ( )является операцией применения комбинаторной логики . (Префикс 1соответствует левой скобке, правые скобки не нужны для устранения неоднозначности.)

Таким образом, существует четыре эквивалентные формулировки BCL, в зависимости от способа кодирования триплета (K, S, левая скобка). Это (00, 01, 1)(как в настоящей версии), (01, 00, 1), (10, 11, 0), и (11, 10, 0).

Операционная семантика BCL, за исключением эта-редукции (которая не требуется для полноты по Тьюрингу ), может быть очень компактно задана следующими правилами переписывания для подтермов данного термина, разбирая их слева:

где x, yи z— произвольные подтермы. (Заметим, например, что поскольку синтаксический анализ выполняется слева, 10000не является подтермом 11010000.)

Один шаг правила 110 клеточных автоматов в SK-Basis (написано на языке Wolfram Language ). [3]

BCL можно использовать для копирования алгоритмов, таких как машины Тьюринга и клеточные автоматы . [3] BCL является полным по Тьюрингу .

Смотрите также

Ссылки

  1. ^ ab Tromp, John (2007), «Двоичное лямбда-исчисление и комбинаторная логика», Случайность и сложность (PDF) , World Sci. Publ., Хакенсак, Нью-Джерси, стр. 237–260, CiteSeerX  10.1.1.695.3142 , doi :10.1142/9789812770837_0014, ISBN 978-981-277-082-0, г-н  2427553.
  2. ^ Девайн, Шон (2009), «Прозрение алгоритмической энтропии», Энтропия , 11 (1): 85–110, Bibcode : 2009Entrp..11...85D, doi : 10.3390/e11010085 , MR  2534819
  3. ^ abc Вольфрам, Стивен (2021-12-06). "Комбинаторы: взгляд на столетие". writings.stephenwolfram.com . Архивировано из оригинала 2020-12-06 . Получено 2021-02-17 .

Дальнейшее чтение

Внешние ссылки