THUE — строкопереписывающий интерпретатор
Программа
Готово.
Как это работает
Программа состоит из правил вида лево::=право, по одному на строку, и заканчивается пустой строкой-правилом, содержащей только ::=. Всё, что идёт после этой строки — начальное состояние программы.

На каждом шаге интерпретатор случайно выбирает одно из правил, чья левая часть встречается где-то в текущем состоянии, и заменяет первое найденное вхождение на правую часть. Если правая часть начинается с ~, весь текст после тильды не подставляется в состояние, а отправляется в поток вывода. Программа останавливается, когда ни одно правило больше не подходит — из-за недетерминизма один и тот же код может каждый раз выполняться по-разному (а иногда и не останавливаться вовсе).

По мотивам Thue Devine Lu Linvega, исходная идея — John Colagioia (2000).
Состояние 0 шагов
Вывод

    
Правила