二項組み合わせ論理

二項組合せ論理（BCL）は、0と1の二項を使用して、記号0と1のみを使用した組合せ論理の完全な定式化を作成するコンピュータプログラミング言語です。 ^{[1] SおよびKコンビネータを使用すると、複雑なブール代数関数を作成できます。BCLは、プログラムサイズの複雑さ（}コルモゴロフ複雑性）の理論に応用されています。 ^{[1] [2]}

組合せ論理のKおよびS組合せ子を利用すると、論理関数は組合せ子の関数として表現できます。

バッカス・ナウア形式:

 <用語>  ::= 00 | 01 | 1 <用語>  <用語>

BCL の表示的セマンティクスは次のように指定できます。

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

ここで、「[...]」は「 の意味」を省略したものです...。ここでK、 と はKS基底コンビネータSであり、 は組合せ論理の適用演算です。(接頭辞は左括弧に対応し、右括弧は曖昧さ回避のために不要です。) ( )1

したがって、3 つ組 (K、S、左括弧) をエンコードする方法に応じて、BCL には 4 つの同等の定式化があります。これらは(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はチューリング完全です。

• イオタとジョット

• トロンプ、ジョン (2007 年 10 月)。「バイナリ ラムダ計算と組み合わせ論理」。ランダム性と複雑性、ライプニッツからチャイティンまで: 237–260。doi : 10.1142 / 9789812770837_0014。ISBN 978-981-277-082-0。
• Tromp, John (2023 年 4 月)。「関数ビット: ラムダ計算に基づくアルゴリズム情報理論」(PDF)。tromp.github.io。

• ジョンのラムダ計算と組み合わせ論理の遊び場
• C言語での最小限の実装
• 383 バイトのラムダ計算
• Brauner, Paul (2018年1月10日). 「Lambda Diagrams YouTube Playlist」. YouTube . 2021年12月21日時点のオリジナルよりアーカイブ。