¿Es realmente posible tener un lenguaje de programación 'útil' que no esté completo en Turing?

Cuando se acepta que un lenguaje tiene que ser Turing completo para ser bueno, ¿es realmente posible tener un lenguaje de programación 'útil' que no sea Turing completo?

Debo aclarar que esto se trata específicamente de lenguajes de 'programación' en el sentido tradicional, y no de lenguajes de marcado o consulta.

Coq , Agda , HOL y ACL2 son lenguajes muy útiles y extremadamente potentes, aunque no son completos para Turing.

Una característica común que los hace no completos de Turing es el hecho de que siempre es posible probar la terminación. Una limitación muy simple es suficiente: las llamadas recursivas solo se permiten en términos demostrablemente estructuralmente más pequeños. Por lo tanto, si bien no es posible implementar un intérprete para un lenguaje completo de Turing o incluso para el lenguaje en sí, muchas otras cosas útiles aún son posibles, como un compilador de C certificado .

Creo que el término "mini-idioma" de Yegge se refiere al hecho de que a menudo es útil usar un idioma para problemas específicos en los que el idioma no requiere la integridad completa para realizar la tarea, y esto va al corazón de cómo no -durante idiomas completos puede ser útil. https://sites.google.com/site/steveyegge2/language-grubbing

Wikipedia responde muy bien a esto, justo en línea con lo que dijo mi instinto. Primero estaba pensando en matemática pura, luego recordé regexp, y Wikipedia enumera Epigram que creo que estaría en la línea de 'matemática pura'.

http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages

Idiomas no completos de Turing

Existen muchos lenguajes computacionales que no están completos en Turing. Un ejemplo de ello es el conjunto de lenguajes regulares, más comúnmente expresiones regulares, que son generados por autómatas finitos. Una extensión más potente pero aún no completa de Turing de autómatas finitos es la categoría de autómatas pushdown y gramáticas libres de contexto, que se usan comúnmente para generar árboles de análisis en una etapa inicial de compilación del programa. Otros ejemplos incluyen algunas de las primeras versiones de los lenguajes de sombreadores de píxeles integrados en las extensiones Direct3D y OpenGL, o una serie de fórmulas matemáticas en una hoja de cálculo sin ciclos. [Cita requerida] En los lenguajes de programación funcional total, todas las funciones son totales y deben terminar, como Caridad y Epigrama. Charity utiliza un sistema de tipos y construcciones de control basadas en la teoría de categorías,

Lenguajes de datos

La noción de integridad de Turing no se aplica a lenguajes como XML, JSON, YAML y expresiones S, porque generalmente se usan para representar datos estructurados, no para describir la computación. A veces se los conoce como lenguajes de marcado, o más propiamente como "lenguajes de descripción de datos".

También menciona que las representaciones de la estructura de datos no son lenguajes, pero creo que XSLT debería contar como una representación de la computación, XPath tal vez no se base en lo que Yannis dijo anteriormente acerca de que SQL es un lenguaje de consulta y no un lenguaje de computación. Tal vez T-SQL o PL / SQL cuenten como lenguajes de cálculo, ya que puede hacer una gran cantidad de cálculos utilizando sus agregados, donde la forma generalizada de SQL quizás no especifique agregados.

Entiendo que SQL es bastante popular entre los tipos de negocios

La integridad de Turing es necesaria para que un idioma sea apto para su uso como lenguaje de propósito general. Pero no es suficiente , es decir, solo porque está completo, no es adecuado para todos los dominios problemáticos:

• Se ha comprobado que el espacio en blanco es Turing completo, pero obviamente no es adecuado para ningún dominio problemático fuera del entretenimiento del programador.
• Se ha demostrado que las plantillas de C ++ están completas, pero nunca escribirías programas completos con ellas.

Por el contrario, un DSL es adecuado para el dominio del problema para el que fue diseñado (suponiendo que, de hecho, fuera decente), incluso sin la integridad de Turing:

• HTML ^* proporciona una forma concisa de describir un árbol DOM. Si bien JavaScript está Turing completo y se puede utilizar para hacer lo mismo, es mucho más ruidoso y poco claro
• XPath y otros lenguajes de consulta, PCRE sin código incrustado y tales son todas herramientas poderosas para el único trabajo para el que fueron diseñadas

^* IIRC se demostró que HTML con animaciones CSS está completando Turing al usarlos para implementar el Juego de la vida de Conway en una variedad de casillas de verificación. Pero la utilidad de HTML se mantiene incluso en navegadores que no admiten animaciones CSS.

En realidad existen lenguajes de programación, donde solo puedes escribir programas "eficientes". Eficiente en este sentido significa que cada programa escrito en dicho idioma representa un idioma en P. Bellantoni, Niggl y Schwichtenberg describen tal lenguaje aquí .

El preprocesador C no está completo de Turing (por diseño), pero aún puede implementar un intérprete para un lenguaje que está completo de Turing (Ordenar el lenguaje, como se describe en la documentación, es básicamente una simple ejecución) Muela algo puramente funcional del tipo ML / Scheme, y sería relativamente poco notable, probablemente bastante agradable de usar, si no fuera por la implementación inusual).

El truco detrás de esto es similar a los argumentos anteriores sobre la implementación de cualquier máquina de Turing en un universo físico finito: el preprocesador C no puede proporcionar un número infinito de pasos o celdas de datos al lenguaje, pero puede:

1. proporciona un número dinámico irracionalmente grande (2 ^ 64 más o menos de forma predeterminada), lo suficientemente grande como para resolver los problemas más realistas mediante un proceso de expansión exponencial ( murmullo murmullo vida del universo murmullo ).

2. use un límite estático arbitrario para el número anterior, es decir, aunque el número de pasos debe ser un número finito, puede cambiar el límite específico en el momento de "compilación" cambiando la configuración estática del motor del intérprete. Como no hay un límite (teórico) en el valor real de este límite, puede (en teoría) extenderse para adaptarse al requisito de espacio para cualquier programa de terminación.

No para argumentar que Order es necesariamente "útil" en sí mismo, o que cualquier motor implementado por CPP lo sería, pero es una prueba de concepto interesante. También se supone que se escribe dinámicamente , lo cual es inusual en esta área.

Sí, de hecho es posible tener un lenguaje útil que no esté completo en Turing. Ver aquí: http://tkatchev.bitbucket.org/tab/examples.html

Otro ejemplo de un lenguaje incompleto útil de Turing es SQL. (Y otro más son las hojas de cálculo como Gnumeric o Excel, aunque en realidad no son lenguajes de programación).

En cuanto a por qué querría un lenguaje que no sea completo para Turing: porque eso le permite hacer algunas garantías sólidas sobre el comportamiento en tiempo de ejecución.

La integridad de Turing, en pocas palabras, significa tener capacidad de recurrencia. Tener recursividad significa tener estructuras potencialmente ilimitadas en la memoria. Dado que en el mundo real la memoria no es infinita, la integridad de Turing requiere gestión de memoria y / o recolección de basura.

Prohibir la recursividad es una excelente manera de evitar el problema realmente difícil de la gestión de recursos.

Nota bene! Estar Turing incompleto no implica necesariamente que cualquier programa necesariamente terminará. Un lenguaje incompleto de Turing podría permitir evaluar una lista perezosa infinita.

Un interesante "lenguaje de programación sub-Turing" no se mencionó hasta ahora, así que lo agregaré.

Se llama "Crema" . Se describe a sí mismo como:

Crema es un front-end LLVM que tiene como objetivo ejecutarse específicamente en el espacio completo sub-Turing. Diseñado para ser simple de aprender y práctico para la mayoría de las tareas de programación necesarias, Crema puede restringir la complejidad computacional del programa al mínimo necesario para mejorar la seguridad.

Es bastante minimalista y de nivel bastante bajo.

Debería ser algo familiar para los desarrolladores de C.

Inicialmente fue financiado por la Agencia de Proyectos de Investigación Avanzada de Defensa (DARPA), pero parece bastante inmaculado en el momento de la escritura. Pero tal vez alguien está interesado, sin embargo.