He visto sitios web que pretenden "probar" que HTML5 + CSS es Turing Complete.
He visto sitios web que pretenden "probar" que SQL está Turing completo.
He visto un montón de sitios web que pretenden "explicar" lo que significa ser Turing completo.
¡Suficiente!
¿Dónde puedo encontrar un libro? como una máquina de Turing "?
Respuestas:
Cada lenguaje que puede implementar dos contadores (es decir, dos registros que pueden almacenar dos enteros arbitrariamente grandes) y un programa hecho con una secuencia etiquetada de estas dos instrucciones elementales es Turing completo:C1,C2
El resultado se demuestra en:
Marvin L. Minsky, "La indisolución recursiva del problema de la etiqueta de Post y otros temas en la teoría de las máquinas de Turing" (1961)
No olvide que un modelo computacional (en su caso, un lenguaje de programación + un dispositivo que ejecuta programas escritos en ese lenguaje ) puede considerarse Turing completo solo si admite el acceso a una cantidad ilimitada de memoria (es decir, espacio) o puede almacenar ( en alguna forma) enteros arbitrariamente grandes. Una implementación de lenguaje de programación en una computadora real es equivalente a un autómata lineal .
También puede encontrar muchas referencias en las páginas de Wikipedia sobre el modelo RAM y el modelo RASP .
Finalmente un buen libro enfocado en la equivalencia de diferentes modelos de computación es:
"Modelos de computación: una introducción a la teoría de la computabilidad", por Maribel Fernández
fuente
Los dos libros de texto más utilizados sobre computabilidad y teoría de la complejidad son:
También hay una hermosa monografía de filosofía para laicos que trabaja a través de los detalles técnicos de la teoría de la computabilidad sin las pruebas formales.
Finalmente, la mejor introducción a la computabilidad puede ser un libro de rompecabezas de un lógico famoso:
(Comienza con un montón de acertijos basados en la paradoja del mentiroso, y luego te ayuda a construir una declaración autorreferencial bajo la apariencia de un rompecabezas al estilo de Sherlock Holmes sobre una misteriosa caja cerrada).
fuente