¿Existen criterios mínimos para que un lenguaje de programación sea Turing completo?

¿Existe un conjunto de construcciones de lenguaje de programación en un lenguaje de programación para que pueda considerarse Turing Complete?

Por lo que puedo decir de Wikipedia , el lenguaje debe admitir la recursividad o, al parecer, debe poder ejecutarse sin detenerse. ¿Es esto todo lo que hay que hacer?

Siempre pensé que las funciones recursivas lograron . Esto es lo que define todo el conjunto de funciones computables; Es el conjunto más pequeño de funciones que contienen resp. cerrado contra:$\mu$

1. La constante función$0$
2. La función sucesora
3. Seleccionar parámetros
4. Composición de la función
5. Recursion primitiva
6. El operador (busque la más pequeña de tal manera que ...)$\mu$$x$

Verifique el enlace de arriba para más detalles; ves que es un lenguaje de programación muy compacto. También es horrible programarlo, no hay almuerzo gratis. Si deja caer cualquiera de esos, perderá toda la potencia, por lo que es un conjunto mínimo de axiomas.

Puede traducirlos literalmente en elementos sintácticos básicos para los programas WHILE , a saber

1. El constante 0
2. Incremento _ + 1
3. Acceso variable x
4. Programa / concatenación de declaraciones _; _
5. Bucles de cuenta regresiva for ( x to 0 ) do _ end
6. Mientras bucles while ( x != 0 ) do _ end

¿Existe un conjunto de cálculos que deben ser ejecutables en un lenguaje de programación para que se considere Turing completo?

Sí, para que Turing se considere completo, un lenguaje de programación debe ser capaz de realizar cualquier cálculo que pueda realizar una máquina de Turing. Por lo tanto, como requisito mínimo se podría decir, debe poder implementar una máquina Turing universal, o un intérprete para cualquier otro lenguaje completo de Turing, en él.

Por lo que puedo decir de Wikipedia, el lenguaje debe admitir la recursividad o, al parecer, debe poder ejecutarse sin detenerse. ¿Es esto todo lo que hay que hacer?

No. Por ejemplo, un lenguaje donde la única operación permitida es la recursión (es decir, la única función posible que puede escribir es f(x) = f(x)que no está completada por Turing porque todo lo que puede escribir en él son programas que nunca terminan. Como dije antes, un lenguaje completo de Turing necesita poder implementar cualquier cálculo que pueda realizar una máquina de Turing. Claramente, eso no es suficiente.

Además, un lenguaje no tiene que soportar la recursividad en la forma en que estás pensando. Solo una forma irrestricta de expresar bucles. Eso podría ser recurrencia, pero también podría ser un bucle while o ir a. Un lenguaje que no tiene funciones en absoluto puede ser Turing completo. Y nuevamente, los bucles o las funciones recursivas no son una condición suficiente. Aún necesita una forma de ejecutar código diferente según una condición y una forma de calcular nuevos valores a partir de los antiguos (de lo contrario, todos los bucles / recursiones serían infinitos o no se ejecutarían en absoluto).

En cuanto a si hay un conjunto mínimo de operaciones necesarias y suficientes, de modo que cualquier lenguaje que admita estas operaciones esté completo y cualquier lenguaje que no lo sea: No, no lo hay (a menos que defina "operación" de forma tan vaga) , que deja de tener sentido):

Por ejemplo, como ya dije, hay lenguajes completos de Turing que no admiten funciones recursivas (o ninguna función). Esos todavía pueden estar completos en Turing si tienen una gotodeclaración o un whilebucle (y una forma de almacenar cantidades arbitrarias de datos). Sin embargo, un lenguaje con funciones recursivas no necesita whileni gotoser Turing completo. Por gotolo tanto , no estaría en el conjunto de operaciones suficientes necesarias, pero hay idiomas que ya no se completarán si se eliminan goto. Por lo tanto, no existe tal conjunto.

Hay varias instrucciones individuales que conducen a los idiomas completos de Turing. El ejemplo típico es "restar y ramificar si es cero". Estos son bien conocidos en el contexto de la programación en lenguaje ensamblador. Vea el artículo de Wikipedia para más detalles.

Esto lleva a una caracterización: un lenguaje es Turing completo si y solo si es capaz de simular las operaciones de buscar y almacenar enteros en la memoria y realizar la operación "restar y ramificar si cero" en ellos.

Esta no es una respuesta general a su pregunta, pero según el teorema de programación estructurada , todo lo que se necesita es la capacidad de hacer selección (por ejemplo, ifen C / C ++) y repetición (por ejemplo, whileen C / C ++). Editar: como señaló Dave Clarke en los comentarios, el teorema de programación estructurada también requiere secuencia. Inicialmente no enumeré esto, dado que daba por sentado que el lector entendería que también eran necesarios bloques básicos de otras instrucciones, como las mencionadas más adelante para leer y escribir en el almacén de memoria, etc. Por supuesto, es mejor ser explícito; también necesitas poder hacer estas cosas.

Dado que ambos pueden implementarse utilizando una instrucción de salto condicional (por ejemplo, JNZen x86), eso también es suficiente para la equivalencia de Turing.

Tenga en cuenta que se requieren otras cosas, es decir, la capacidad de escribir un número ilimitado de símbolos (por ejemplo, bits ... 0 o 1) en algún tipo de almacén de memoria externa. En ese sentido, las computadoras reales no son equivalentes a Turing, ya que ninguna de ellas tiene una cantidad infinita de almacenamiento. Sin embargo, el modelo de Turing sigue siendo útil, ya que la cantidad de memoria suele ser enorme, y aunque cualquier problema que una computadora real pueda resolver puede resolverse mediante un autómata finito determinista, usar ese modelo de cálculo no es particularmente útil (ya que número de estados sería ridículamente enorme).

Tenga en cuenta que esto no está necesariamente en desacuerdo con la respuesta de sepp2k; Esta es una forma diferente de pensar sobre la misma pregunta.

EDITAR:

Tenga en cuenta también que realmente no necesita ambos ify whileen C / C ++. Puede simular ifusando whilelo siguiente:

bool C;
// some code that sets C
if(C) { /* some other code /* }
// rest of the program

El siguiente código siempre es equivalente:

bool C;
// some code that sets C
bool C2 = C;
while(C2) { /* some other code /* C2 = false; }
// rest of the program

Bueno ... la construcción debería funcionar y ser posible si tienes cuidado, eso es. Tenga en cuenta también que si tiene funciones recursivas, eventualmente necesita selección también; Como las funciones recursivas sin selección realmente no pueden implementar casos base, cualquier función recursiva daría como resultado una recursión infinita.

EDITAR:

Además, con respecto a su pregunta sobre si la capacidad de escribir un programa que no se detenga es suficiente para la equivalencia de Turing, la respuesta es no; Es necesario, pero no suficiente. Podemos resolver el problema de detención de programas escritos en un lenguaje que no puede expresar programas que no se detienen; la respuesta es "el programa se detiene" para todas las instancias. Sin embargo, podemos definir un idioma donde la única instrucción hace que la máquina entre en un bucle infinito ... tal lenguaje no es equivalente a Turing.

Los combinadores y donde, y son suficientes para expresar cualquier término lambda (cerrado), por lo tanto, cualquier función computable. Vea esta página de Wikipedia para más detalles.K ( S x y z ) = ( x z ( y z ) ) ( K x y ) = $\mathbf{S}$$\mathbf{K}$$(\mathbf{S}\ x\ y\ z) = (x\ z\ (y\ z))$$(\mathbf{K}\ x\ y) = x$

De hecho, el término lambda es una base suficiente para expresar todos los términos lambda. Ver más adelante en la misma página de Wikipedia .$\mathbf{X}=\lambda x.((x\ \mathbf{S})\ \mathbf{K})$

Las construcciones del lenguaje son intercambiables.

No hay un criterio mínimo establecido sobre qué construcciones debe proporcionar de forma nativa un lenguaje de programación. Si proporciona algunas construcciones extrañas que de alguna manera pueden ser complicadas para expresar un sistema completo de Turing, entonces aparentemente esas construcciones son "tan adecuadas" como cualquier otra.

Para probar esto, un lenguaje que proporciona solo una operación de "resta y ramificación si cero" es Turing completo; existen lenguajes completos de Turing que no proporcionan una construcción separada "restar y ramificar si cero", por lo tanto, no hay una construcción o un conjunto de construcciones que sea obligatorio.

Los efectos de cualquier construcción de lenguaje TP-completo pueden ser emulados por las construcciones de cualquier otro lenguaje TP-completo.