Йота и Джот

Йота, Джот, Зот
Парадигмы	Формальный язык , Тьюринговский туман , эзотерический
Разработано	Крис Баркер
Разработчик	Крис Баркер
Впервые появился	2001 год ; 23 года назад
Окончательный релиз	2001 г. / 2001 ; 23 года назад
Язык реализации	Схема , JavaScript
Платформа	Интерпретатор схем, веб-браузер (JavaScript)
Лицензия	Всеобщее достояние
Веб-сайт	www .ню .edu /проекты / Баркер
Под влиянием
	Зот

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

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

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

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

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

( 1 )

Отсюда можно восстановить обычные выражения SKI , таким образом:

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

( 2 )

Из-за своего минимализма он повлиял на исследования постоянной Чайтина . ^[2]

Йота [ править ]

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

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

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

Йот [ править ]

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

Джот  =   ""   |    запись  "0"   |    буква  "1"

Семантика задается переводом в выражения SKI. Пустая строка обозначает $I$ , $w0$ обозначает $(([w]S)K)$ , где $[w]$ это перевод $w$ , и $w1$ обозначает $(S(K[w]))$ .

Суть $w1$ дело в том, что перевод удовлетворяет $(([w1]A)B)=([w](AB))$ для произвольных условий SKI $A$ и $B$ . Например,

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

справедливо для произвольных строк

w

. Сходным образом,

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

держится также. Эти два примера представляют собой базовые случаи перевода произвольных терминов SKI в Jot, данные Баркером: делая Jot естественной гёделевой нумерацией всех алгоритмов .

Джот связан с Йотой тем, что $[w0]=(\iota [w])$ и используя те же тождества в терминах SKI для получения базовых комбинаторов $K$ и $S$ .

Зот [ править ]

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

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

где 1 производит продолжение $\lambda cL.L(\lambda lR.R(\lambda r.c(lr)))$ , и 0 производит продолжение $\lambda c.c\iota$ , и $wi$ потребляет последнюю входную цифру $i,$ продолжая выполнение продолжения $w$ .

См. также [ править ]

Ссылки [ править ]

^ Баркер, Крис. «Зот» . Вебринг «Эзотерические языки программирования» . Архивировано из оригинала 12 марта 2016 года . Проверено 4 октября 2016 г.
^ Останься, Майкл (август 2005 г.). «Очень простые чайтиновые машины для бетона AIT» . Фундамента информатики . 68 (3). ИОС Пресс: 231–247. arXiv : cs/0508056 . Бибкод : 2005cs........8056S . Проверено 20 февраля 2011 г.

Внешние ссылки [ править ]

Официальный веб-сайт
Баркер, Крис. «Йота и Йот: простейшие языки?» . Вебринг «Эзотерические языки программирования» . Архивировано из оригинала 23 августа 2016 года . Проверено 13 августа 2004 г.
https://esolangs.org/wiki/Iota
https://esolangs.org/wiki/Jot
https://esolangs.org/wiki/Zot

[1] Баркер, Крис. «Зот» . Вебринг «Эзотерические языки программирования» . Архивировано из оригинала 12 марта 2016 года . Проверено 4 октября 2016 г.

[2] Останься, Майкл (август 2005 г.). «Очень простые чайтиновые машины для бетона AIT» . Фундамента информатики . 68 (3). ИОС Пресс: 231–247. arXiv : cs/0508056 . Бибкод : 2005cs........8056S . Проверено 20 февраля 2011 г.

[1]

[2]