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

37

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.

PhonicUK
fuente
3
@PhonicUK SQL no estaba completo al principio
Ryathal
44
@Ryathal SQL no es un lenguaje de programación, es un lenguaje de consulta.
Yannis
2
@PhonicUK su pregunta en comentario realmente vale la pena, cambie la pregunta publicada a eso o se cerrará como no constructiva. En realidad, hay idiomas completos útiles que no son de duración, y me interesaría escuchar detalles de ellos.
Jimmy Hoffa
55
expresiones regulares no es Turing completo, sin embargo, es ampliamente utilizado
trinquete monstruo
3
@DavidHammen Las implementaciones reales son limitadas, sí, debido a los límites de nuestro universo físico (solo puede construir memoria finita, solo puede ejecutar la máquina por un tiempo limitado antes de que funcione mal). Pero eso no significa que los idiomas sean limitados. IOW la especificación de un lenguaje completo no requiere una implementación para imponer dichos límites en un programa, mientras que un lenguaje que no sea TC requiere, por ejemplo, una prueba de terminación.

Respuestas:

48

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 .

SK-logic
fuente
2
Para aquellos que no están familiarizados con esos idiomas, ¿podrían entrar en más detalles sobre lo que les falta que los hace no completos de Turing, y algunos ejemplos de cosas construidas con esos idiomas?
PhonicUK
8
@PhonicUK: un compilador de C no es una aplicación C . Es una herramienta que transforma el código en un lenguaje (C) en otro (generalmente código de máquina). Eso no significa que el compilador de C en sí sea equivalente a cualquier programa de C aleatorio.
Joachim Sauer
99
@PhonicUK, no puede implementar un intérprete para un lenguaje completo de Turing en uno que no sea completo. Pero, por supuesto, puede implementar un compilador (ya que una CPU completa de Turing realizará una evaluación real).
SK-logic
11
@ SK-logic: "¿Por supuesto?" Solo es posible para C porque es un lenguaje bastante simple. No es posible para C ++ porque un compilador tiene que interpretar el código de la plantilla (que es Turing completo en tiempo de compilación).
MSalters
11
@MSalters Sí, si la compilación del idioma está completa, un compilador debe estar escrito en un idioma completo. Lo que también es algo obvio (por no decir tautológico). Sin embargo, tenga en cuenta que el estándar C ++ permite límites en los programas de entrada, como una profundidad de evaluación máxima para las instancias de plantilla (y las implementaciones existentes se toman esta libertad). Si no me equivoco, esto significa que puede ser posible un compilador completo de C ++ que no sea duradero (por supuesto, salvo problemas no relacionados).
12

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.

Jimmy Hoffa
fuente
8

Entiendo que SQL es bastante popular entre los tipos de negocios

Martin Beckett
fuente
3
SQL es un lenguaje de consulta, no un lenguaje de programación.
PhonicUK
44
@PhonicUK: ¿y cuál es exactamente la diferencia entre un lenguaje de consulta y un lenguaje de programación?
Joachim Sauer
8
@PhonicUK - Tex es un lenguaje de marcado de texto y está completando Turing
Martin Beckett
3
Las implementaciones modernas de SQL, hasta donde yo sé, se están completando.
shabunc
66
@shabunc IIRC solo con procedimientos almacenados. El argumento se vuelve un poco circular, si no es Turing completo, entonces no es un lenguaje de programación, por lo tanto, todos los lenguajes de "programación" son TC
Martin Beckett
5

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.

back2dos
fuente
2
¿Tienes un enlace a Conway's Life implementado en CSS?
RBerteig
No sé de una implementación de CGOL en CSS, pero sé que se implementó la Regla 110. Sin embargo, parece que no puedo encontrarlo, parece que se ha movido.
Christian Mann
-1 Muy interesante pero no aborda la pregunta formulada
mattnz
2
@mattnz: Incorrecto. Doy ejemplos concretos de lenguajes no completos de Turing que son útiles, lo que creo que es una respuesta apropiada a "¿Es realmente posible tener un lenguaje de programación 'útil' que no sea completo de Turing?", No muy diferente de otra respuesta aquí
back2dos
3

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í .

SpaceTrucker
fuente
1

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.

Leushenko
fuente
Voto por murmurar en medio de la conferencia.
jpaugh
-1

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.

tkatchev
fuente
-1

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.

Mateusz Kowalewski
fuente