¿qué tan útil es la integridad de Turing? ¿están completas las redes neuronales turing?

Turing-integridad de las redes neuronales recurrentes podría significar: las tablas de transición (finitas) de todas y cada una de las máquinas de Turing (con una cabeza de estado finito y una cinta infinita) pueden ser modeladas por una red neuronal recurrente finita (finitamente muchas neuronas con finitamente muchos estados, especialmente solo dos estados). Las tablas de transición definen tres funciones:

• Next-state (current-state,current-symbol)

• Símbolo siguiente (estado actual, current-symbol)

• Dirección (current-state,current-symbol)

Así es como una red neuronal recurrente puede realizar esta tarea (solo un bosquejo muy crudo):

Las neuronas verdes leen el símbolo en la celda actual (en representación binaria), las neuronas grises (initalmente mudas) determinan el estado actual, las neuronas rojas escriben el nuevo símbolo en la celda actual, las neuronas amarillas determinan si ir a la izquierda o a la derecha. Las neuronas azules son las neuronas internas (inicialmente mudas).

La afirmación es, que para todas y cada una de las máquinas de Turing hay una red neuronal recurrente.

Me pregunto si hay una manera sistemática de construir tal red a partir de tablas de transición dadas.

Cuando se dice que las computadoras modernas son Turing Completo hay una excepción tácita para el dispositivo de almacenamiento infinito Turing descrito, que es obviamente una imposibilidad en un dispositivo de cálculo físico finito. Si un dispositivo de cálculo puede hacer todo lo que una máquina de Turing puede hacer (almacenamiento infinito no soportando) es Turing completo para todos los propósitos prácticos. Por esta definición menos estricta de Turing completitud , sí, es posible que muchos las redes neuronales son Turing completo .

Por supuesto, es posible crear uno que no sea Turing completo.

Para abordar parcialmente su segunda pregunta:

Las redes neuronales tienen la propiedad de ser aproximadores universales - es decir, pueden aproximar cualquier función a un grado arbitrario de precisión. Es la parte del "grado de precisión" que evita que la Red Neuronal necesite ser infinita.

Las redes neuronales regulares de feedforward no están completas. Son, en efecto, equivalentes a una sola función matemática complicada que puede hacer bastantes cálculos pero no tiene ninguna habilidad para realizar bucles u otras operaciones de control de flujo.

Sin embargo, si conecta una red neuronal con alguna forma de acceder a un entorno con estado, entonces se puede convertir en una máquina completa de turing.

Como un ejemplo más trivial, podría recrear un máquina de Turing de estilo clásico donde:

• la entrada a la red neuronal es el valor en la cinta y el estado anterior
• la salida de la red neuronal es el siguiente estado y la acción

Entonces podría entrenar a la red neuronal para emular las acciones de cualquier tabla / configuración de estado de la máquina de turing deseada (¿quizás mediante el aprendizaje supervisado de las acciones de otra máquina de turing?)

Nota: La idea de ejecutar una red feedforward repetidamente con alguna forma de retroalimentación de estado es esencialmente equivalente a una red neuronal recurrente. Así que puedes pensar en una red neuronal recurrente más la lógica que la ejecuta repetidamente como Turing completa. Necesita la lógica adicional (más allá de la propia red) para garantizar la integridad de Turing porque es necesario manejar cosas como terminación, repetición e IO.

Creo que el concepto de integridad de Turing no pretende decirnos si una computadora en particular puede realizar una tarea en particular.

Más bien, pretende decir si un lenguaje en particular es capaz de expresar una tarea en particular. Es decir, yo diría que realmente se trata de expresar un algoritmo no realizarlo.

Como las redes neuronales no tienen un lenguaje, se trata de expresar un algoritmo en términos de una red neuronal, en lugar de capacidad de esa red. ¡Así que no se la respuesta a la última parte de tu pregunta!

Creo que un punto importante sobre la máquina de turing es que para cualquier dada entrada y programa, la máquina solo necesitará una cantidad finita de cinta, suponiendo que se detenga algún tiempo. Es por eso que diría que el término "turing completo" es útil: Solo necesita memoria finita para ejecutar un programa turing completo específico en alguna entrada específica (si el programa se detiene). Pero si tiene una máquina/lenguaje/tecnología no completa de turing, no podrá simular ciertos algoritmos, no importa cuánta memoria añades.

Casi siempre es bueno saber qué clase en la jerarquía de Chomsky es su sistema. Esto es especialmente importante en las clases más restringidas, como lenguajes regulares / autómatas finitos vs lenguajes libres de contexto. También es importante tener la habilidad de reconocer en qué clase está el problema que está tratando de resolver, de lo contrario uno podría intentar hacer cosas tontas como analizar HTML o XML solo con expresiones regulares, lo cual es imposible.

Tener el conocimiento de que su formalismo o sistema es turing completa hace una declaración de que se puede construir lo que quieras con él. No dice nada sobre la practicidad, solo la posibilidad o imposibilidad de resolver problemas. Esto es dolorosamente cierto cuando se considera turing tarpits, pero también hay muchos sistemas completos de turing que están hechos específicamente para propósitos de nicho que nadie debería soñar con usar para trabajos de propósito general en un entorno de producción.

En resumen, buen conocimiento de la Chomsky la jerarquía le ayudará en muchas situaciones, no solo para elegir el tipo correcto de analizador; regexp, pushdown, CFG o más potente, sino también para elegir el tipo correcto de máquina o formalismo para expresar procesos en general.

Básicamente significa que con el lenguaje de programación o la arquitectura que están Turing completa
puede ejecutar una amplia variedad de algoritmos... en su mayoría any cualquier tipo de ellos.

Las lenguas que no son de Turing tienen un potencial mucho más estrecho.

La respuesta es muy simple. Si puedes emular una puerta NOR o NAND con ella, entonces es Turing Completo, asumiendo que el resto es solo una cuestión de combinar cosas.