Jota i Jot

Jota, Jot, Zot
Paradygmaty	Język formalny , Tarpit Turinga , ezoteryczny
Zaprojektowany przez	Chrisa Barkera
Deweloper	Chrisa Barkera
Po raz pierwszy pojawiły się	2001 ; 22 lata temu
Ostateczne wydanie	2001 / 2001 ; 22 lata temu
Język implementacji	Schemat , JavaScript
Platforma	Interpreter schematów, przeglądarka internetowa (JavaScript)
Licencja	Domena publiczna
Strona internetowa	www.nyu.edu/projects/barker _ _ _ _
Pod wpływem
	Zota

W teorii języka formalnego i informatyce , jota i jot (z greckiego iota ι , hebr . rachunek lambda i rachunek kombinacyjny SKI . Tym samym można je również uznać za minimalistyczne języki programowania komputerowego lub tarpity Turinga , ezoteryczne języki programowania zaprojektowane tak, aby były jak najmniejsze, ale wciąż kompletne w Turingu . Oba systemy używają tylko dwóch symboli i obejmują tylko dwie operacje. Oba zostały stworzone przez profesora lingwistyki Chrisa Barkera w 2001 roku. Zot (2002) jest następcą Iota, który obsługuje wejście i wyjście.

Zauważ, że w tym artykule użyto formy Backusa-Naura do opisania składni.

Jota uniwersalna

Uniwersalny kombinator jota Chrisa Barkera $ι$ ma zdefiniowaną tutaj bardzo prostą strukturę λf.fSK, używającą semantyki denotacyjnej w kategoriach rachunku lambda ,

{\ Displaystyle \ jota: = \ lambda f. ((fS) K): = \ lambda f. ((f \ lambda a. \ lambda b. \ lambda c. ((ac) (bc))) \ lambda d .\red. lambda)}

()

Z tego można odzyskać zwykłe wyrażenia SKI , a więc:

{\ Displaystyle I \ = \, (\ jota \ jota) ,\;K\,=\,(\iota (\iota (\iota \iota ))),\;S\,=\,(\iota (\iota (\iota (\iota \iota )))) }

()

Ze względu na swój minimalizm wpłynął na badania dotyczące stałej Chaitina .

Odrobina

Iota to język LL(1) , który prefiksuje drzewa rzędów wspomnianych liści uniwersalnego kombinatora jota $ι ,$ konsekwencją zastosowania funkcji $ε$ ,

     jota  =  "1"  |  „0”  jota jota

więc na przykład 0011011 oznacza ${\ Displaystyle ((\ jota \ jota) (\ jota \ jota)}}$ , podczas gdy 0101011 oznacza ${\ styl wyświetlania (\iota (\iota (\iota \iota)))}$ .

Krztyna

Jot jest językiem regularnym składającym się ze wszystkich sekwencji 0 i 1,

      jot  =  ""  |  kropka  „0”  |  kropka  „1”

Semantyka jest nadawana przez tłumaczenie na wyrażenia SKI. Pusty ciąg oznacza $($ gdzie $Displaystyle$ ( $([w] S) K)}$ , gdzie ${\ Displaystyle [w ]}$ jest tłumaczeniem i oznacza $displaystyle w1}$ $\$ ${\ Displaystyle (S (K [w]))}$ .

${\ displaystyle w1}$ przypadku jest to, że tłumaczenie spełnia ${\ Displaystyle (([w1] A) B) = ([w] (AB))}$ dla dowolnych terminów SKI ${\ displaystyle A}$ i ${\ displaystyle B}$ . Na przykład,

{\ Displaystyle [w11100] = (([w1110] S) K)=(((([w111]S)K)S)K)=((([w11](SK))S)K)=(([w1]((SK)S))K)=( [w](((SK)S)K))=([w]K)}

dotyczy dowolnych ciągów

{\ displaystyle w}

. Podobnie,

{\ Displaystyle [w11111000] = (((((([w11111] S) K) S) K) S) K) = ([w] (((((SK) S) K) S) K ))=([w]S)}

trzyma również. Te dwa przykłady to podstawowe przypadki tłumaczenia dowolnych terminów SKI na Jot podane przez Barkera, co czyni Jot naturalną numeracją Gödla wszystkich algorytmów .

Jot jest połączony z Iota przez fakt, że ${\ Displaystyle [w0] = (\ jota [w])}$ i używając tych samych tożsamości na warunkach SKI w celu uzyskania podstawowych kombinatorów ${ \ displaystyle K}$ i ${\ displaystyle S}$ .

Zot

Języki Zot i Positive Zot wykonują obliczenia Iota , od wejść do wyjść w stylu przekazywania kontynuacji , w składni przypominającej Jot ,

  
  
    zot  =  garnek  |  ""  garnek  =  jot  |  pot jot  jot  =  "0"  |  „1”

0 gdzie 1 daje kontynuację ${\ Displaystyle \ lambda cL.L (\ lambda lRR (\ lambda rc (lr)))}$ i tworzy kontynuację ${\ Displaystyle \ lambda cc \ jota}$ i $wi$ zużywa ostatnią cyfrę wejściową $i$ kontynuując przez kontynuację $w$ .

Zobacz też

Linki zewnętrzne

Oficjalna strona internetowa
Barker, Chris. „Jota i Jot: najprostsze języki?” . Ezoteryczne języki programowania Webring . Zarchiwizowane od oryginału w dniu 7 maja 2016 r . Źródło 13 sierpnia 2004 .
https://esolangs.org/wiki/Iota
https://esolangs.org/wiki/Jot
https://esolangs.org/wiki/Zot