Из Википедии, свободной энциклопедии
  (Перенаправлено из двоичного лямбда-исчисления )
Перейти к навигации Перейти к поиску

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

Определение [ править ]

SK Basis [ править ]

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

Список логических операций как двоичных комбинаторов [3]
Булева алгебраSK Basis
Правда (1)К (КК)
Ложь (0)К (К (СК)) S
ИSSK
НЕТСС (S (S (S (SK)) S)) (KK)
ИЛИ ЖЕS (СС) S (СК)
NANDS (S (K (S (SS (K (KK))))))) S
НИS (S (S (SS (K (K (KK))))) (KS))
XORS (S (S (SS) (S (S (SK))) S)) K

Синтаксис [ править ]

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

 < термин >  :: = 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.)

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

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

См. Также [ править ]

Ссылки [ править ]

  1. ^ a b Тромп, Джон (2007), «Бинарное лямбда-исчисление и комбинаторная логика», Случайность и сложность (PDF) , World Sci. .. Опубл, Хакенсак, Нью - Джерси, стр 237-260, CiteSeerX  10.1.1.695.3142 , DOI : 10.1142 / 9789812770837_0014 , ISBN 978-981-277-082-0, Руководство по ремонту  2427553.
  2. ^ Devine, Шон (2009), "Понимание , алгоритмической энтропии", энтропия , 11 (1): 85-110, DOI : 10,3390 / e11010085 , МР 2534819 
  3. ^ a b c Вольфрам, Стивен (2021-12-06). «Комбинаторы: взгляд столетия» . Writings.stephenwolfram.com . Проверено 17 февраля 2021 .

Дополнительная литература [ править ]

  • Тромп, Джон (октябрь 2007 г.). «Двоичное лямбда-исчисление и комбинаторная логика». Случайность и сложность, от Лейбница до Чайтина: 237–260. DOI : 10.1142 / 9789812770837_0014 .

Внешние ссылки [ править ]

  • Площадка для лямбда-исчисления и комбинаторной логики Джона
  • Минимальная реализация на C