Йота и Йот

Эзотерические языки программирования
Йота, Йот, Зот
ПарадигмыФормальный язык , Тьюринговая тарпита , эзотерический
РазработаноКрис Баркер
РазработчикКрис Баркер
Впервые появился2001 ; 24 года назад ( 2001 )
Окончательный релиз
2001 / 2001 ; 24 года назад ( 2001 )
Язык реализацииСхема , JavaScript
ПлатформаИнтерпретатор схем, веб-браузер (JavaScript)
ЛицензияОбщественное достояние
Веб-сайтweb.archive.org/web/20181024173237/http://www.nyu.edu/projects/barker/Iota/
Под влиянием
Зот

В формальной теории языка и информатике , Iota и Jot (от греческого iota ι, еврейского yodh י, самые маленькие буквы в этих двух алфавитах) являются языками, чрезвычайно минималистскими формальными системами , разработанными так, чтобы быть даже проще, чем другие более популярные альтернативы, такие как лямбда-исчисление и комбинаторное исчисление SKI . Таким образом, их также можно считать минималистскими языками программирования , или Turing tarpits , эзотерическими языками программирования, разработанными так, чтобы быть как можно меньше, но все же полными по Тьюрингу . Обе системы используют только два символа и включают только две операции. Обе были созданы профессором лингвистики Крисом Баркером в 2001 году. Zot (2002) является преемником Iota, который поддерживает ввод и вывод. [1]

Обратите внимание, что в этой статье для описания синтаксиса используется форма Бэкуса-Наура .

Универсальная йота

Универсальный йота-комбинатор ι Криса Баркера имеет очень простую структуру λf.fSK, определенную здесь, с использованием денотационной семантики в терминах лямбда-исчисления ,

Из этого можно восстановить обычные выражения SKI , например:

Благодаря своему минимализму он оказал влияние на исследования, касающиеся постоянной Хайтина . [2]

Йота

Iota — это язык LL(1) , который префиксно упорядочивает деревья вышеупомянутых универсальных листьев комбинатора iota ι , получаемых с помощью применения функции ε ,

йота =  "1"  |  "0"  йота йота

так что например0011011 обозначает , тогда как ( ( й й ) ( й й ) ) {\displaystyle ((\iota \iota)(\iota \iota))} 0101011 обозначает . ( й ( й ( й й ) ) ) {\displaystyle (\iota (\iota (\iota \iota)))}

Йот

Jot — это регулярный язык, состоящий из всех последовательностей 0 и 1,

джот =  ""  |  джот "0"  |  джот "1"

Семантика задается переводом в выражения SKI. Пустая строка обозначает , обозначает , где — перевод , а обозначает . я {\displaystyle Я} ж 0 {\displaystyle w0} ( ( [ ж ] С ) К ) {\displaystyle (([w]S)K)} [ ж ] {\displaystyle [ш]} ж {\displaystyle w} ж 1 {\displaystyle w1} ( С ( К [ ж ] ) ) {\displaystyle (S(K[w]))}

Суть случая в том, что перевод удовлетворяет для произвольных терминов SKI и . Например, выполняется для произвольных строк . Аналогично выполняется также. Эти два примера являются базовыми случаями перевода произвольных терминов SKI в Jot, заданными Баркером, что делает Jot естественной гёделевской нумерацией всех алгоритмов . ж 1 {\displaystyle w1} ( ( [ ж 1 ] А ) Б ) = ( [ ж ] ( А Б ) ) {\displaystyle (([w1]A)B)=([w](AB))} А {\displaystyle А} Б {\displaystyle Б} [ ж 11100 ] = ( ( [ ж 1110 ] С ) К ) = ( ( ( ( [ ж 111 ] С ) К ) С ) К ) = ( ( ( [ ж 11 ] ( С К ) ) С ) К ) = ( ( [ ж 1 ] ( ( С К ) С ) ) К ) = ( [ ж ] ( ( ( С К ) С ) К ) ) = ( [ ж ] К ) {\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} [ ж 11111000 ] = ( ( ( ( ( ( [ ж 11111 ] С ) К ) С ) К ) С ) К ) = ( [ ж ] ( ( ( ( ( С К ) С ) К ) С ) К ) ) = ( [ ж ] С ) {\displaystyle [w11111000]=(((((([w11111]S)K)S)K)S)K)=([w](((((SK)S)K)S)K))=([w]S)}

Jot связан с Iota тем, что и с помощью тех же тождеств в терминах SKI для получения основных комбинаторов и . [ ж 0 ] = ( й [ ж ] ) {\displaystyle [w0]=(\iota [w])} К {\displaystyle К} С {\displaystyle S}

Зот

Языки Zot и Positive Zot управляют вычислениями Iota , от входных данных до выходных данных с использованием стиля продолжения-передачи , в синтаксисе, напоминающем Jot,

зот =  горшок |  "" горшок =  йот |  горшок iot iot =  "0"  |  "1"

где1 производит продолжение , и λ с Л . Л ( λ л Р . Р ( λ г . с ( л г ) ) ) {\displaystyle \lambda cL.L(\lambda lR.R(\lambda rc(lr)))} 0 производит продолжение , а wi потребляет последнюю входную цифру i , продолжая через продолжение w . λ с . с й {\displaystyle \лямбда cc\йота }

Смотрите также

Ссылки

  1. ^ Баркер, Крис. "Zot". The Esoteric Programming Languages ​​Webring . Архивировано из оригинала 12 марта 2016 года . Получено 4 октября 2016 года .
  2. Stay, Michael (август 2005 г.). «Очень простые машины Chaitin для бетона AIT». Fundamenta Informaticae . 68 (3). IOS Press: 231– 247. arXiv : cs/0508056 . Bibcode : 2005cs........8056S. doi : 10.3233/FUN-2005-68303 . Получено 20 февраля 2011 г.
  • Официальный сайт
  • Баркер, Крис. «Йота и Йота: простейшие языки?». The Esoteric Programming Languages ​​Webring . Архивировано из оригинала 23 августа 2016 г. Получено 13 августа 2004 г.
  • https://esolangs.org/wiki/Йота
  • https://esolangs.org/wiki/Jot
  • https://esolangs.org/wiki/Zot
Взято с "https://en.wikipedia.org/w/index.php?title=Йота_и_Йот&oldid=1271449917"