Thue

Thue () — эзотерический язык программирования, разработанный  в начале 2000 года. Это мета-язык, который демонстрирует нулевой тип в иерархии Хомского, то есть неограниченную грамматику. Thue позволяет определять любые языки и является полным по Тьюрингу.

Автор описывает его следующим образом:
«Thue представляет собой простейшую демонстрацию программирования в ограничениях. Именно за счёт этой парадигмы язык аналогичен языкам URISC императивной парадигмы. Другими словами это Тьюринговская трясина».

Правила 
Программа на языке Thue состоит из таблицы правил и начального состояния.
Таблица правил состоит из простых определений вида

 A ::= B

A и B могут состоять как из отдельных букв и символов так и из их групп.
Может существовать множество правил с одинаковым A и разными B.
Таблица правил заканчивается пустым правилом:

 ::=

Начальное состояние представляет собой строку символов, записанную после таблицы правил.

Работа программы состоит в поиске исходных (левых) символов и замене их на правые в соответствии с правилом.

Работа завершается когда к строке нельзя применить ни одного правила.

Таким образом программа на Thue аналогична машине Тьюринга: имеется лента символов и имеется набор правил по которым они заменяются.

Недетерминированность 
Одна из ключевых особенностей языка заключается в недетерминированном порядке выбора.

Если в строке имеется несколько символов, к которым может быть применено правило, то оно будет применено к случайно выбранному символу.

Если определено несколько правил для одного символа, то будет применено случайно выбранное правило.

Ввод / вывод 
Для реализации ввода и вывода в языке есть особая форма правил.
Для вывода символов используется тильда:

 A::=~строка символов

Это правило убирает A из строки и выводит все символы, идущие после тильды.

Для ввода три двоеточия:

 A::=:::

Это правило заменяет A на строку, прочитанную из ввода.

Примеры программ 
«Hello World!» на Thue:

 a::=~Hello World!
 ::=
 a

В языке нет переменных как понятия. Поэтому для каких-либо вычислений нужно задавать соответствующие системы правил.
Следующая программа демонстрирует инкрементацию двоичного числа (увеличение на единицу). Число записано символьно и отмечено по краям знаком подчёркивания:

 1_::=1++
 0_::=1
 
 01++::=10
 11++::=1++0
 
 _0::=_
 _1++::=10
 
 ::=
 
 _1111111111_

Детерминизм обеспечивается наличием лишь одного правила и лишь одного символа, к которому его можно применить в каждый конкретный момент времени.

Следующая программа демонстрирует реализацию циклов и недетерминизм правил:

 b::=~0
 b::=~1
 xx::=xbx
 ::=
 xbx

Эта программа выводит бесконечную строку единиц и нулей.
Цикличность обеспечивается следующим образом: после каждого вывода символ b удаляется из строки xbx, оставшиеся символы xx заменяются на xbx, воспроизводя начальное состояние.
Таким образом возможно создание ограниченных циклов, число итераций которых задаётся числом определённых символов или наборов символов в строке:

 _x::=i_
 i::=~test!
 ::=
 _xxxxx

Эта программа 5 раз выведет строку test!
Обратите внимание, что порядок замены i и _x при этом неопределён. То есть в процессе выполнения программа может как сразу обрабатывать i по мере их появления, так и выбрать из строки все x сразу.

См. также 
 Нормальные алгоритмы Маркова

Ссылки 
 Страница языка
 Thue на esolangs
 Очень подробная статья о языке с рассмотрением различных задач и решений
 Интерпретатор Thue на JavaScript

Языки программирования по алфавиту
Эзотерические языки программирования
Языки программирования, появившиеся в 2000 году