El lenguaje de los while
programas puede expresar las funciones computablemente enumerables. (Esto es cierto incluso si las únicas operaciones aritméticas en variables son, por ejemplo, incremento y decremento).
Si while
se reemplaza por for
hacer bucles siempre delimitados, el lenguaje solo puede expresar las funciones recursivas primitivas.
Recientemente me di cuenta de la clase de funciones elementales , que están estrictamente por debajo de las funciones recursivas primitivas, pero todavía estrictamente por encima de la jerarquía exponencial.
Obviamente, sería posible definir un lenguaje de programación imperativo que capture exactamente las funciones elementales, por ejemplo, introduciendo operadores para la suma limitada y el producto. Sin embargo, mi pregunta es:
¿Existe un cambio sintáctico en el lenguaje de los
while
programas que lo restringe a las funciones elementales y que puede expresarse tan simplemente como la restricción (while
->for
) a las funciones recursivas primitivas?
Una restricción a for
programas en lugar también bastaría, por supuesto, y tal vez debería aclarar que no estoy buscando algo que está absolutamente como se ha dicho con sencillez, sólo algo con simplicidad comparables que no requiere la adición de operadores adicionales o similares .
Editar : Un ejemplo de for
lenguaje representativo es PL- {GOTO} de "Theory of Computation" (1974) de Brainerd y Landweber, en el que cada programa tiene un número finito pero sin restricciones de variables, cada una de las cuales puede contener un número natural, y que consiste esencialmente en los siguientes comandos:
X <- 0
(asignar 0 a una variable)X <- Y
(asigne el valor deY
aX
)X <- Y + 1
(asigne el sucesor del valor deY
aX
)LOOP X; ... END;
(repite el bloque deX
tiempos de código contenido ; no se modificaX
)
Los autores dan una prueba de que esto puede expresar exactamente las funciones recursivas primitivas. El lenguaje PL no coincide perfectamente con la pregunta, ya que utiliza en GOTO
lugar de while
, y PL- {GOTO} se deriva de PL al eliminarlo GOTO
. Sin embargo, los programas de PL son tan poderosos como while
los programas, y esta GOTO
transformación: extracción es tan simple como la sustitución declararon while
con for
. (Posiblemente quizás incluso un poco más simple).
Edición 2 : http://en.wikipedia.org/wiki/Total_Turing_machine sugiere que este resultado se remonta a: Meyer, AR, Ritchie, DM (1967), La complejidad de los programas de bucle , Proc. de las Reuniones Nacionales de la ACM, 465.
fuente
for
bucles, pero nunca he visto una prueba. ¿Tienes?LOOP
(lo que he llamadofor
) comoGOTO
Turing completo, pero que sinGOTO
él solo puede expresar las funciones pr. Editaré la pregunta para incluir una breve descripción de este idioma.