Iota och Jot

Iota, Jot, Zot

Paradigm	Formellt språk , Turing tarpit , esoteriskt
Designad av	Chris Barker
Utvecklare	Chris Barker
Dök först upp	2001 ( 2001 )
Slutlig utgåva	2001 / 2001 ( 2001 )
Implementeringsspråk	Scheme , JavaScript
Plattform	Schematolk, webbläsare (JavaScript)
Licens	Allmängods
Hemsida	www .nyu .edu /projects /barker
Influerade
Zot

Inom formell språkteori och datavetenskap är Iota och Jot (från grekiska iota ι, hebreiska yodh י, de minsta bokstäverna i dessa två alfabet) språk, extremt minimalistiska formella system , designade för att vara ännu enklare än andra mer populära alternativ, som t.ex. lambdakalkylen och SKI kombinatorkalkylen . Således kan de också betraktas som minimalistiska datorprogrammeringsspråk , eller Turing tarpits , esoteriska programmeringsspråk designade för att vara så små som möjligt men ändå Turing-kompletta . Båda systemen använder bara två symboler och involverar endast två operationer. Båda skapades av professorn i lingvistik Chris Barker 2001. Zot (2002) är en efterföljare till Iota som stöder input och output.

Observera att den här artikeln använder Backus-Naur-formen för att beskriva syntax.

Universal iota

Chris Barkers universella jota-kombinator ι har den mycket enkla λf.fSK-strukturen definierad här, med hjälp av denotationssemantik i termer av lambdakalkylen ,

$\iota :=\lambda f.((fS)K):= \lambda f.((f\lambda a.\lambda b.\lambda c.((ac)(bc)))\lambda d.\lambda ed)$

 

 

 

 

()

Från detta kan man återställa de vanliga SKI-uttrycken , således:

$I\,=\,(\iota \iota ) ,\;K\,=\,(\iota (\iota (\iota \iota ))),\;S\,=\,(\iota (\iota (\iota (\iota \iota )))))$

 

 

 

 

()

På grund av dess minimalism har den påverkat forskningen om Chaitins konstanta .

Iota

Iota är LL(1) -språket som prefix ordnar träden för de ovannämnda Universal jota ι kombinatorbladen, koncentrerad av funktionsapplikationen ε ,

     iota  =  "1"  |  "0"  jota jota 

så att till exempel 0011011 betecknar $((\iota \iota )(\iota \iota ))$ , medan 0101011 betecknar $) displaystyle (\iota (\iota (\iota \iota )))}$ .

Anteckna

Jot är det vanliga språket som består av alla sekvenser av 0 och 1,

      jot  =  ""  |  ange  "0"  |  anteckna  "1" 

Semantiken ges genom översättning till SKI-uttryck. Den tomma strängen betecknar $I$ , $w0$ betecknar $(([w]S)K)$ , där $[w ]$ är översättningen av $w$ , och $w1$ betecknar $(S(K[w]))$ .

Poängen med $w1$ -fallet är att översättningen uppfyller $(([w1]A)B)= ([w](AB))$ för godtyckliga SKI-termer $A$ och $B$ . Till exempel,

$$[w11100]=(([w1110 ]S)K)=(((([w111]S)K)S)K)=((([w11](SK))S)K)=(([w1]((SK)S))K )=([w](((SK)S)K))=([w]K)$$

håller för godtyckliga strängar $w$ . Liknande,

$$[w11111000]=((((((([w11111]S)K)S)K)S)K)=([w](((((SK)S)K) S)K))=([w]S)$$

håller också. Dessa två exempel är basfallen för översättningen av godtyckliga SKI-termer till Jot givna av Barker, vilket gör Jot till en naturlig Gödel-numrering av alla algoritmer .

Jot är kopplat till Iota genom att $[w0]=(\iota [w])$ och genom att använda samma identiteter på SKI-termer för att erhålla de grundläggande kombinatorerna ${ \displaystyle K}$ och $S$ .

Zot

Språken Zot och Positiva Zot beordrar Iota -beräkningar , från ingångar till utgångar genom fortsättningsöverförande stil , i syntax som liknar Jot ,

  
  
    zot  =  pott  |  ""  pott  =  iot  |  pot iot  iot  =  "0"  |  "1" 

0 där 1 ger fortsättningen ${\displaystyle \lambda cL.L(\lambda lR.R(\lambda rc(lr)))} ,$ och producerar fortsättningen $\lambda cc\iota$ , och wi förbrukar den sista inmatade siffran i genom att fortsätta genom fortsättningen w .

Se även

• Lambdakalkyl
• Kombinationslogik
• Binär kombinatorisk logik
• SKI kombinatorkalkyl

externa länkar

• Officiell hemsida
• Barker, Chris. "Iota och Jot: de enklaste språken?" . Webringen för esoteriska programmeringsspråk . Arkiverad från originalet den 7 maj 2016 . Hämtad 13 augusti 2004 .
• https://esolangs.org/wiki/Iota
• https://esolangs.org/wiki/Jot
• https://esolangs.org/wiki/Zot