二項組み合わせ論理

コンピュータプログラミング言語

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

意味

SKベーシス

組み合わせ論理のKおよびSコンビネータを利用すると、論理関数はコンビネータの関数として表現できます。

二項結合子としての論理演算の一覧^[3]
	ブール代数	SKベーシス
	真実(1)	K(KK)
	誤り(0)	K(K(SK))
	そして	SSK
	ない	SS(S(S(S(SK))S))(KK)
	または	S(SS)S(SK)
	ナンド	S(S(K(S(SS(K(KK)))))))S
	または	S(S(S(SS(K(K(KK)))))(KS))
	排他的論理和	S(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、左括弧）の符号化方法に応じて、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はチューリング完全です。

参照

イオタとジョット

参考文献

^ ab Tromp, John (2007)、「バイナリラムダ計算と組み合わせ論理」、ランダム性と複雑性(PDF)、World Sci. Publ.、Hackensack、NJ、pp. 237– 260、CiteSeerX 10.1.1.695.3142、doi :10.1142/9789812770837_0014、ISBN 978-981-277-082-0、MR 2427553。
^ ディヴァイン、ショーン（2009）「アルゴリズム的エントロピーの洞察」、エントロピー、11（1）：85-110、Bibcode：2009Entrp..11...85D、doi：10.3390/e11010085、MR 2534819
^ abc Wolfram, Stephen (2021年12月6日). 「コンビネータ：100周年の視点」writings.stephenwolfram.com . arXiv : 2103.12811 . 2020年12月6日時点のオリジナルよりアーカイブ。 2021年2月17日閲覧。

さらに読む

トロンプ、ジョン（ 2007年10月）「二項ラムダ計算と組合せ論理」『ランダム性と複雑性、ライプニッツからチャイティンまで』 237-260頁。doi : 10.1142/9789812770837_0014。ISBN 978-981-277-082-0。
ジョン・トロンプ（2023年4月）「関数ビット：ラムダ計算に基づくアルゴリズム情報理論」（PDF） .tromp.github.io.

外部リンク

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

[tromp-1] Tromp, John (2007)、「バイナリラムダ計算と組み合わせ論理」、ランダム性と複雑性(PDF)、World Sci. Publ.、Hackensack、NJ、pp. 237– 260、CiteSeerX 10.1.1.695.3142、doi :10.1142/9789812770837_0014、ISBN 978-981-277-082-0、MR 2427553。

[2] ディヴァイン、ショーン（2009）「アルゴリズム的エントロピーの洞察」、エントロピー、11（1）：85-110、Bibcode：2009Entrp..11...85D、doi：10.3390/e11010085、MR 2534819

[:0-3] Wolfram, Stephen (2021年12月6日). 「コンビネータ：100周年の視点」writings.stephenwolfram.com . arXiv : 2103.12811 . 2020年12月6日時点のオリジナルよりアーカイブ。 2021年2月17日閲覧。