¿Puede un idioma ser completo sin ningún soporte para matrices?

Question

Si un lenguaje tiene estructuras de control y variables, pero no admite matrices, listas, acceso a memoria y asignación, etc., ¿puede ser Turing-complete?

Tal vez si no había límite a la cantidad de variables que se pueden crear, se puede simular matrices mediante la creación de variables como array_1, array_2, ... array_6000 y manualmente bucle a través de ellos, y de alguna manera crear estructuras de datos complejas y recursividad?

Editar: incluso si no puede acceder a las variables por manipulación de nombres (array_10+i no está permitido)?

Answer 1

Ciertamente. Eche un vistazo a Lambda Calculus, que es uno de los idiomas más mínimos de Turing Complete que he visto. Básicamente, todo lo que tienes son lambdas (literales de función); sin asignación, sin declaración, sin estructuras de datos. Todo es muy, muy delgado.

Sin embargo, puede simular una estructura de datos lineal como una Lista encadenando funciones juntas. Se vuelve bastante detallado, pero ciertamente es posible y es mucho mejor que tener una gran serie de variables nombradas secuencialmente.

En general, si un idioma es o no es Turing Complete no tiene nada que ver con si tiene matrices. ¡Los lenguajes funcionales como SML y Haskell carecen de arreglos, al igual que Lambda Calculus, y estos son en realidad idiomas útiles! Decir que un idioma es "Turing completo" es simplemente otra forma de decir que no existe una función computable de Turing que no pueda expresarse en dicho lenguaje. Esta es una calificación sorprendentemente flexible, que permite muchos idiomas que serían completamente imprácticos (como el cálculo de Lambda).

Answer 2

¡Hay muchos lenguajes completos de Turing que ni siquiera tienen la noción de "variable"! El acceso a la memoria y las asignaciones son detalles de implementación, por lo que son completamente irrelevantes. Debes darte cuenta de que las máquinas de Turing y la completitud de Turing son conceptos muy teóricos, útiles para probar cosas, pero completamente divorciados de la realidad del hardware real.

Paul Graham ha escrito mucho, pero muy, muy interesante essay sobre la historia de los lenguajes de programación en el que describe las dos principales tradiciones muy diferentes de los lenguajes de programación:

• Lisp, Scheme, etc. - derivados desde consideraciones teóricas, lenguajes muy simples, pero conceptualmente potentes, pero impracticables durante mucho tiempo por su completo desprecio por lo que es fácil y eficiente de implementar
• Ensamblador, FORTRAN, C y casi todos los lenguajes "principales" - derivaron más o menos directamente de lo que el hardware podría hacer, fácil de implementar, eficiente, pero para el el tiempo más largo inferior a la familia de Lisp (¡más antigua!) en términos de expresividad.

Parece que usted conoce solo la segunda tradición, pero la completitud de Turing es un concepto que se origina de los mismos principios que la primera tradición y tiene poco sentido si no conoce esos principios.