Thue ( / t ü eɪ / DEMASIADO -ay ) es un lenguaje de programación esotérico inventado por John Colagioia a principios de 2000. Es un metalenguaje que se puede utilizar para definir o reconocer Type-0 Idiomas de la jerarquía de Chomsky . Debido a que es capaz de definir lenguajes de tal complejidad, también es Turing-complete en sí mismo. Thue se basa en un sistema de reescritura de cadenas no determinista llamado gramática semi-Thue , que a su vez lleva el nombre del matemático noruego Axel Thue. . El autor lo describe de la siguiente manera: "Thue representa una de las formas más simples posibles de interpretar la programación basada en restricciones . Es para el paradigma basado en restricciones lo que lenguajes como OISC son para el paradigma imperativo; en otras palabras, es un pozo de alquitrán . "
Thue consume los símbolos iniciales y sustituye el resultado de las reglas por cada uno de los símbolos del estado inicial.
Cuando se invoca con 'd' (depuración), imprime el estado. Cuando se invoca con 'l' (lado izquierdo), aplique las reglas de izquierda a derecha. Cuando se invoca con 'r' (lado derecho), aplique las reglas de derecha a izquierda. La última 'l' o 'r' anula los interruptores anteriores.
El siguiente programa Thue realiza un incremento de un número binario ingresado como estado inicial rodeado por caracteres "_", en este caso el número 1111111111:
El siguiente programa de muestra es para demostrar el no determinismo de Thue (y para mostrar un ejemplo de un bucle infinito, además). El programa genera bits en una secuencia indefinida (y posiblemente aleatoria).