Парадигмы | Формальный язык , Тьюринговая тарпита , эзотерический |
---|---|
Разработано | Крис Баркер |
Разработчик | Крис Баркер |
Впервые появился | 2001 ( 2001 ) |
Окончательный релиз | 2001 / 2001 ( 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, определенную здесь, с использованием денотационной семантики в терминах лямбда-исчисления ,
1 |
Из этого можно восстановить обычные выражения SKI , например:
2 |
Благодаря своему минимализму он оказал влияние на исследования, касающиеся постоянной Хайтина . [2]
Iota — это язык LL(1) , который префиксно упорядочивает деревья вышеупомянутых универсальных листьев комбинатора iota ι , получаемых с помощью применения функции ε ,
йота = "1" | "0" йота йота
так что например0011011 обозначает , тогда как0101011 обозначает .
Jot — это регулярный язык, состоящий из всех последовательностей 0 и 1,
джот = "" | джот "0" | джот "1"
Семантика задается переводом в выражения SKI. Пустая строка обозначает , обозначает , где — перевод , а обозначает .
Суть случая в том, что перевод удовлетворяет для произвольных терминов SKI и . Например, выполняется для произвольных строк . Аналогично выполняется также. Эти два примера являются базовыми случаями перевода произвольных терминов SKI в Jot, заданными Баркером, что делает Jot естественной гёделевской нумерацией всех алгоритмов .
Jot связан с Iota тем, что и с помощью тех же тождеств в терминах SKI для получения основных комбинаторов и .
Языки Zot и Positive Zot управляют вычислениями Iota , от входных данных до выходных данных с использованием стиля продолжения-передачи , в синтаксисе, напоминающем Jot,
зот = горшок | "" горшок = йот | горшок iot iot = "0" | "1"
где1 производит продолжение , и0 производит продолжение , а wi потребляет последнюю входную цифру i , продолжая через продолжение w .