Binární kombinační logika - Binary combinatory logic

Binární kombinační logika ( BCL ) je počítačový programovací jazyk, který pomocí binárních výrazů 0 a 1 vytváří úplnou formulaci kombinační logiky pouze pomocí symbolů 0 a 1. Pomocí kombinátorů S a K lze vytvářet komplexní booleovské funkce algebry. BCL má aplikace v teorii složitosti velikosti programu ( Kolmogorovova složitost ).

Definice

Základna SK

S využitím kombinátorů K a S kombinační logiky mohou být logické funkce zastoupeny jako funkce kombinátorů:

Syntax

Forma Backus – Naur :

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

Sémantika

K Denotační sémantika BCL mohou být specifikovány takto:

• [ 00 ] == K
• [ 01 ] == S
• [ 1 <term1> <term2> ] == ( [<term1>] [<term2>] )

kde „ [...]“ zkracuje „význam ...“. Tady Ka Sjsou Ks -basis kombinátory , a ( )je aplikace operace, o kombinační logiky . (Předpona 1odpovídá levé závorce, pravá závorka je pro disambiguation zbytečná.)

Existují tedy čtyři ekvivalentní formulace BCL v závislosti na způsobu kódování tripletu (K, S, levá závorka). Jsou to (00, 01, 1)(jako v tomto provedení), (01, 00, 1), (10, 11, 0), a (11, 10, 0).

Tyto operační sémantika Bcl, na rozdíl od eta-redukce (která není potřebná pro Turing úplnost ), může být velmi kompaktní, o které po přepisovacích pravidel pro subterms daného termínu, analýze zleva:

•  1100xy  → x
• 11101xyz → 11xz1yz

kde x, ya zjsou libovolné subterms. (Všimněte si například toho, že protože analýza probíhá zleva, 10000není podmětem 11010000.)

Jeden krok pravidla 110 celulárních automatů na bázi SK (psáno jazykem Wolfram ).

BCL lze použít k replikaci algoritmů, jako jsou Turingovy stroje a mobilní automaty , BCL je Turing dokončen .

Viz také

• Iota a Jot

Reference

Další čtení

• Tromp, John (říjen 2007). „Binární lambda kalkul a kombinační logika“. Náhodnost a složitost, od Leibniz po Chaitin : 237–260. doi : 10,1142/9789812770837_0014 .

externí odkazy

• John's Lambda Calculus and Combinatory Logic Playground
• Minimální implementace v C
• Brauner, Paul. „Seznamy videí Lambda na YouTube“ .