Criterios para determinar si se trata de un lenguaje de programación

Question

¿Cuáles son los critera o las características básicas que se requieren para decirle que X o Y es (o ¿no) un lenguaje de programación?

que he hecho alguna lectura (Is HTML considered a programming language?, Turing complete y others), y llegó a la conclusión de que una lengua o una sintaxis tiene que ser Turing completa para ser considerado un lenguaje de programación. ¿Es esto correcto? ¿Es suficiente?

¿Y cómo puedo determinar si algo es Turing complete? ¿Hay algún criterio específico?

Tiene estructuras de control de flujo (instrucciones condicionales y bucles) suficientes para considerarse Turing complete?

Answer 1

El término "lenguaje de programación" es algo borroso. ¿Las expresiones regulares constituyen un lenguaje de programación? La mayoría de los programadores dirían que sí, a pesar de que las expresiones regulares no están completas.

En cuanto a la completitud de Turing, no soy un experto, pero creo que es suficiente tener una rama condicional y una pila infinita (por lo tanto, la máquina real solo se aproxima a la completitud).

EDIT: Después de un poco de investigación, he encontrado que esto no es suficiente. Necesita al menos dos pilas y una cantidad mínima de estados (y una tabla de transición de estado).

Tal vez una medida más realista es que si se pueden recordar cantidades arbitrarias de estados y bucles, es probable que se haya completado.

Answer 2

Existen lenguajes de programación que no están completos. Para ver algunos ejemplos de lenguajes completos que no son de Turing, consulte: Practical non-Turing-complete languages?

Una ventaja de tener un lenguaje que no es completo de Turing podría ser, por ejemplo, que podría ser suficiente para realizar las tareas que necesita, mientras lo suficientemente simple como para permitirle probar propiedades sobre sus programas, que de otro modo no podría probar. Esto podría, por ejemplo, ser útil en casos donde es vital saber que el programa se ejecutará sin error.

Lo que constituye exactamente un lenguaje de programación es un poco vago, pero podría decirse que es un lenguaje en el que puede expresar cálculos. Si miramos HTML, no puede crear un documento que compute nada; simplemente le dice al navegador cómo se supone que debe verse la página. La parte importante a tener en cuenta es que no computa nada nuevo.

Es, como dice Marcelo, bastante borroso.

En cuanto a la determinación de si una lengua es Turing completo, voy a referirlo a esta pregunta: What are practical guidelines for evaluating a language's "Turing Completeness"?

Answer 3

¿Cuáles son los critera o las características básicas que se requieren para decir que X o Y es (o no es) un lenguaje de programación?

Como Marcelo Cantos ya se dijo es algo difusa, sobre todo porque hay dominio de idiomas específicos (DSL; http://en.wikipedia.org/wiki/Domain-specific_language) que no son Turing completo, pero los lenguajes de programación también a menudo considerados.

¿Y cómo puedo determinar si algo está completo? ¿Hay algún criterio específico?

Una forma de determinar si un lenguaje de programación es Turing completo es escribir una máquina de Turing en él (o una implementación del cálculo Lambda).

Otra forma es probar que todas las funciones mu recursivas http://en.wikipedia.org/wiki/%CE%9C-recursive_function se pueden calcular mediante el lenguaje de programación.

Como se puede demostrar que un lenguaje de programación imperativo es Turing completo, si hay una asignación variable, una forma de representar el número 0, una función sucesora, una función predecesora y una posibilidad de representar bucles while esta es otra camino.

Una manera a veces utilizada (que por razones obvias no siempre funciona) para probar que un lenguaje de programación no es Turing-completo es comprobar si todos los programas terminan; si es así, no puede ser.

Answer 4

Así que vamos a pensar en las consecuencias de estas definiciones concretas:

Un lenguaje Turing completo es un lenguaje de programación: CSS becomes a programming language.

Un lenguaje de programación debe ser turing-completo: quizás, pero programs can be written otherwise.

Ahora una mejor definición: Un lenguaje de programación es aquel que se puede usar para escribir programas.