Бинарная комбинаторная логика

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

Определение

СК Базис

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

Список логических операций как двоичных комбинаторов ^[3]
	Булева алгебра	СК Базис
	Правда(1)	ХАХАХА)
	Ложь(0)	К(К(СК))
	И	ССК
	НЕТ	СС(С(С(С(СК))С))(КК)
	ИЛИ	С(СС)С(СК)
	NAND	S(S(K(S(СС(К(КК))))))S
	НИ	S(S(S(СС(К(К(КК)))))(КС))
	БЕСПЛАТНО	S(S(S(SS)(S(S(SK)))S))K

Синтаксис

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

 <term> ::= 00 | 01 | 1 <term> <term>

Семантика

Денотационная семантика 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 является полным по Тьюрингу .

См. также

Йота и Джот

Ссылки

^ Jump up to: ^а ^б Тромп, Джон (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 .
^ Дивайн, Шон (2009), «Идея алгоритмической энтропии», Entropy , 11 (1): 85–110, Bibcode : 2009Entrp..11...85D , doi : 10.3390/e11010085 , MR 2534819
^ Jump up to: ^а ^б ^с Вольфрам, Стивен (06 декабря 2021 г.). «Комбинаторы: взгляд на столетие» . сочинения.stephenwolfram.com . Архивировано из оригинала 06 декабря 2020 г. Проверено 17 февраля 2021 г.

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

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

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

Лямбда-исчисление Джона и игровая площадка комбинаторной логики
Минимальная реализация на C
Лямбда-исчисление в 383 байтах
Браунер, Пол. «Плейлист YouTube с лямбда-диаграммами» . Ютуб . Архивировано из оригинала 21 декабря 2021 г.

[tromp-1] Jump up to: ^а ^б Тромп, Джон (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), «Идея алгоритмической энтропии», Entropy , 11 (1): 85–110, Bibcode : 2009Entrp..11...85D , doi : 10.3390/e11010085 , MR 2534819

[:0-3] Jump up to: ^а ^б ^с Вольфрам, Стивен (06 декабря 2021 г.). «Комбинаторы: взгляд на столетие» . сочинения.stephenwolfram.com . Архивировано из оригинала 06 декабря 2020 г. Проверено 17 февраля 2021 г.

[1]

[2]

[3]