イオタとジョット

イオタ、ジョット、ゾット
パラダイム	形式言語、チューリングタールピット、難解
デザイン：	クリス・バーカー
開発者	クリス・バーカー
初登場	2001 （2001年）
最終リリース	2001年 / 2001年 （2001年）
実装言語	Scheme、JavaScript
プラットフォーム	Schemeインタープリタ、Webブラウザ（JavaScript）
ライセンス	パブリックドメイン
Webサイト	ウェブ.archive .org /web /20181024173237 /http: //www .nyu .edu /projects /barker /Iota /
影響を受けた
ゾット

形式言語理論とコンピュータサイエンスにおいて、IotaとJot（ギリシャ語のiota ι、ヘブライ語のyodh יに由来、これら2つのアルファベットの最小の文字）は言語であり、極めて最小限の形式体系で、ラムダ計算やSKIコンビネータ計算などのより一般的な代替言語よりもさらに単純になるよう設計されている 。したがって、これらは最小限のコンピュータプログラミング言語、またはチューリングタールピット、つまり可能な限り小さくてもチューリング完全であるように設計された難解なプログラミング言語と考えることもできる。どちらのシステムも2つの記号のみを使用し、2つの演算のみを伴う。どちらも2001年に言語学教授のクリス・バーカーによって作成された。Zot （2002）は入出力をサポートするIotaの後継である。^{[ 1 ]}

この記事では、構文を説明するためにBackus-Naur 形式を使用していることに注意してください。

ユニバーサルイオタ

クリス・バーカーの普遍イオタコンビネータιは、ラムダ計算の表示的意味論を用いてここで定義された非常に単純なλf.fSK構造を持つ。

${\displaystyle \iota :=\lambda f.((fS)K):=\lambda f.((f\lambda a.\lambda b.\lambda c.((ac)(bc)))\lambda d.\lambda e.d)}$

1

このことから、通常のSKI式を復元することができます。

${\displaystyle I\,=\,(\iota \iota ),\;K\,=\,(\iota (\iota (\iota \iota ))),\;S\,=\,(\iota (\iota (\iota (\iota \iota ))))}$

2

そのミニマリズムのため、チャイティン定数に関する研究に影響を与えた。^{[ 2 ]}

イオタ

イオタは、前述のユニバーサルイオタιコンビネータの葉のツリーを関数適用εによってコンスするLL(1)言語である。

イオタ= "1" | "0"イオタ イオタ

例えば0011011は、 ${\displaystyle ((\iota \iota )(\iota \iota ))}$0101011は を表します。 ${\displaystyle (\iota (\iota (\iota \iota )))}$

メモ

Jotは0と1のシーケンスすべてで構成される 正規言語です。

メモ= "" |メモ"0" |メモ"1"

意味はSKI式への変換によって与えられます。空文字列は を表し、 は を表します。ここでは の変換であり、は を表します。 ${\displaystyle I}$ ${\displaystyle w0}$ ${\displaystyle (([w]S)K)}$ ${\displaystyle [w]}$ ${\displaystyle w}$ ${\displaystyle w1}$ ${\displaystyle (S(K[w]))}$

この場合のポイントは、任意のSKI項とに対して変換が成立することです。例えば、 任意の文字列に対しては成立します。同様に、 も成立します。これら2つの例は、Barkerによって与えられた任意のSKI項からJotへの変換の基本例であり、Jotはすべてのアルゴリズムの自然なゲーデル数となります。 ${\displaystyle w1}$ ${\displaystyle (([w1]A)B)=([w](AB))}$ ${\displaystyle A}$ ${\displaystyle B}$ $${\displaystyle [w11100]=(([w1110]S)K)=(((([w111]S)K)S)K)=((([w11](SK))S)K)=(([w1]((SK)S))K)=([w](((SK)S)K))=([w]K)}$$ ${\displaystyle w}$ $${\displaystyle [w11111000]=(((((([w11111]S)K)S)K)S)K)=([w](((((SK)S)K)S)K))=([w]S)}$$

Jot は、 および という SKI 用語の同じ恒等式を使用して基本コンビネータおよびを取得することにより、 Iota と接続されます。 ${\displaystyle [w0]=(\iota [w])}$ ${\displaystyle K}$ ${\displaystyle S}$

ゾット

Zot言語とPositive Zot言語は、Jotに似た 構文で、継続渡しスタイルによって入力から出力までIotaの計算を実行します。

ゾット=ポット| ""ポット= iot |ポット iot iot = "0" | 「1」

どこ1は継続を生成し、 ${\displaystyle \lambda cL.L(\lambda lR.R(\lambda r.c(lr)))}$0 は継続を生成し、wi は継続wを継続することで最後の入力数字iを消費します。 ${\displaystyle \lambda c.c\iota }$

参照

• ラムダ計算
• 組み合わせ論理
• 二項組み合わせ論理
• SKIコンビネータ計算

参考文献

1. Barker, Chris. 「Zot」 . The Esoteric Programming Languages Webring . 2016年3月12日時点のオリジナルよりアーカイブ。 2016年10月4日閲覧。
2. Stay, Michael (2005年8月). 「コンクリートAITのための非常にシンプルなChaitinマシン」 . Fundamenta Informaticae . 68 (3). IOS Press: 231– 247. arXiv : cs/0508056 . Bibcode : 2005cs......8056S . doi : 10.3233/FUN-2005-68303 . 2011年2月20日閲覧。

外部リンク

• 公式サイト
• バーカー、クリス. 「IotaとJot：最もシンプルな言語？」 . The Esoteric Programming Languages Webring . 2016年8月23日時点のオリジナルよりアーカイブ。 2004年8月13日閲覧。
• https://esolangs.org/wiki/イオタ
• https://esolangs.org/wiki/Jot
• https://esolangs.org/wiki/Zot

「 https://en.wikipedia.org/w/index.php?title=Iota_and_Jot&oldid=1271449917」から取得