¿Qué tan útil es la integridad de Turing? ¿Están completos las redes neuronales?

Question

Mientras lee algunos documentos sobre la integridad de las redes neuronales recurrentes (por ejemplo: la computabilidad de Turing con redes neuronales, Hava T. Siegelmann y Eduardo D. Sontag, 1991), tuve la sensación de que la prueba que se dio no había realmente eso práctico. Por ejemplo, el documento referenciado necesita una red neuronal que la actividad neuronal debe ser de exactitud infinita (para que sea confiable representar cualquier número racional). Otras pruebas necesitan una red neuronal de tamaño infinito. Claramente, eso no es realmente tan práctico.

Pero comencé a preguntarme ahora si tiene sentido pedir turing. Según la definición estricta, ningún sistema informático hoy en día está completo porque ninguno de ellos podrá simular la cinta infinita.

Curiosamente, la especificación del lenguaje de programación lo deja con mayor frecuencia abierto si están completos o no. Todo se reduce a la pregunta si siempre podrán asignar más memoria y si el tamaño de la pila de llamadas de función es infinito. La mayoría de las especificaciones realmente no especifican esto. Por supuesto, todas las implementaciones disponibles son limitadas aquí, por lo que todas las implementaciones prácticas de los lenguajes de programación no están completos.

Entonces, lo que puede decir es que todos los sistemas informáticos son igualmente potentes como máquinas de estado finitas y no más.

Y eso me lleva a la pregunta: ¿Qué tan útil se completa el término Turing?

Y volver a las redes neuronales: para cualquier implementación práctica de una red neuronal (incluido nuestro propio cerebro), no podrán representar un número infinito de estados, es decir, por la definición estricta de integridad, no están completos. Entonces, ¿tiene sentido la pregunta si las redes neuronales están completas?

La pregunta si son tan poderosas como las máquinas estatales finitas ya se respondió mucho antes (1954 por Minsky, la respuesta, por supuesto: sí) y también parece más fácil de responder. Es decir, al menos en teoría, esa ya era la prueba de que son tan poderosos como cualquier computadora.

---

Algunas otras preguntas que son más sobre lo que realmente quiero saber:

• ¿Hay algún término teórico que pueda decir algo más específico sobre el poder computacional de una computadora? (dado su espacio de memoria limitado)

• ¿Cómo puede comparar el poder computacional de las implementaciones prácticas de redes neuronales con las computadoras? (Turing-completar no es útil como se discute anteriormente).

Answer 1

El punto de afirmar que un modelo matemático está completo es revelar la capacidad del modelo para realizar cualquier cálculo, Dada una cantidad suficiente de recursos (es decir, infinito), no mostrar si una implementación específica de un modelo tiene esos recursos. Los modelos completos que no son capaces no podrían manejar un conjunto específico de cálculos, Incluso con suficientes recursos, algo que revela una diferencia en la forma en que operan los dos modelos, Incluso cuando tienen recursos limitados. Por supuesto, para demostrar Esta propiedad debe suponer que los modelos pueden usar una cantidad infinita de recursos, pero Esta propiedad de un modelo es relevante incluso cuando los recursos son limitados.

Answer 2

La satisfacción 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 modelarse mediante una red neuronal recurrente finita (finitamente muchas neuronas con finitas. Estados, especialmente solo dos estados). Las tablas de transición definen tres funciones:

• Next-State (estado de corriente, símbolo de corriente)

• Símbolo siguiente (estado de corriente, símbolo de corriente)

• dirección (estado de corriente, símbolo de corriente)

Así es como una red neuronal recurrente puede realizar esta tarea (solo un boceto muy en bruto):

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

El reclamo es, que Para todas y cada una de las máquinas de Turing hay una red neuronal tan recurrente.

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

Answer 3

Cuando se dice que las computadoras modernas son Turing Complete Hay una excepción tácita para el dispositivo de almacenamiento infinito que se describe, que obviamente es una imposibilidad en un dispositivo de cálculo físico finito. Si un dispositivo de cálculo puede hacer todo lo que puede hacer una máquina Turing (el almacenamiento infinito a pesar de) Turing Complete Para todos los intentos y propósitos prácticos. Por esta definición menos estricta de Turing integridad, sí, es posible que muchas redes neuronales sean Turing Complete.

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

Answer 4

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 el "grado de precisión" que evita que la red neuronal necesite ser infinita.

Answer 5

Las redes neuronales de avance regulares son no turing completo. En efecto, son equivalentes a una sola función matemática complicada que puede hacer muchos cálculos, pero no tiene ninguna capacidad, realice un bucle o otras operaciones de flujo de control.

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

Como un ejemplo muy trivial, puede recrear una máquina de turbación 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 próximo estado y la acción

Luego podría capacitar 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 sobre las acciones de otra máquina de turbios?)

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

Answer 6

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

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

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

Answer 7

Después de muchos años, permítanme dar una respuesta a esta pregunta.

Turing integridad

• Tan potente como una máquina de turbio (TM).
• Requiere un memoria infinita. Es decir, en la práctica, ningún dispositivo físico puede estar completo.
• Considere un normal computadora personal (PC):
  • Una instancia física específica es no Turing Complete, como tiene memoria finita.
  • Sin embargo, considere el concepto de PC Como algo donde podría agregar memoria a pedido. Todos los programas seguirán funcionando de la misma manera cuando agregue más memoria. Para cualquier entrada dada y cualquier programa dado, hay una cantidad máxima de memoria de tal manera que debería funcionar. (No seamos pedantes ahora sobre el int64 Límite de dirección de memoria o cosas así. Estos son límites técnicos, que podrían resolverse, por ejemplo, por grandes ints, etc.) por lo tanto, podemos decir que la concepto de PC está completo.
• La integridad de Turing se trata principalmente del concepto de memoria. Considere cualquier máquina/autómata de estado finito (FSA) y algún acceso a la memoria externa. Dependiendo del tipo de memoria, termina en diferentes clases del Jerarquía de Chomsky:
  • Sin memoria / memoria finita: Idiomas regulares
  • pila única: Autómatas, Idiomas sin contexto
  • Dos o más pilas: Turing Complete, lenguaje recursivamente enumerable

Redes neuronales recurrentes (RNN)

Sobre el poder computacional de las redes neuronales

Un papel a menudo citado es Sobre el poder computacional de las redes neuronales, Siegelmann y Sonntag, 1992, que establece que los rnns están completos. Este artículo supone que tenemos números racionales sin límites en el nominador/denominador, es decir, la memoria infinita está codificada como números racionales o números de punto flotante de precisión infinita. Ver también aquí. Por lo general, no modelamos un NN de una manera que funcione con números racionales (sin límite). Cuando nos restringimos a (r) nns con pesos y activaciones de precisión finitos, la prueba en el documento cae en aparato y ya no se aplica. Por lo tanto, este documento no es tan relevante.

Hay un artículo más reciente, Sobre el poder computacional práctico de los RNN de precisión finito para el reconocimiento del lenguaje, Weiss et al, 2018, que aborda exactamente esto.

Aproximador universal

Es bien sabido que la mayoría de los NN estándar son aproximadores universales. Esto establece que dada cualquier función (no constante, limitada y continua), y dado algún umbral permitido, puede construir una nn que se aproxima a esta función dentro del umbral permitido. Se trata de espacios vectoriales dimensionales finitos. Cuando hablamos de computabilidad, hablamos de secuencias, por lo tanto, tenemos un espacio vectorial dimensional infinito. Por lo tanto, esta propiedad no es tan relevante.

Sin memoria externa

Por lo tanto, para indicarlo explícitamente: sin memoria externa, el RNN estándar y también LSTM es no turing completo. Tampoco hay una forma directa de cómo podrías definir un concepto de un RNN, donde podría agregar memoria a pedido. La memoria de un RNN es las activaciones ocultas más recientes. Agregar más memoria significa cambiar el NN, es decir, agregar nuevas neuronas, agregando así el funcionamiento interno de la misma. Esto es como cambiar el programa en sí.

Con memoria externa

Ahí está el Máquina neural de Turing (NTM) y algunos modelos similares, que tienen algún tipo de memoria externa. Aquí es sencillo pensar en un concepto de un NTM donde agregarías memoria a pedido. Así podemos decir que la concepto de un NTM está completo.

Hay algunos detalles como el tipo de atenciones utilizadas en las cabezas, que necesitan cierta adaptación. Hay un seguimiento del modelo, el Computadora neuronal diferenciable (DNC) que aborda explícitamente esto, y también tiene algún mecanismo explícito para agregar memoria.

Aprendizaje / capacitación

Hablamos principalmente sobre el poder de cálculo teórico. Una pregunta muy diferente es si el NN puede aprender tal función. Es decir, si la capacitación (búsqueda de gradiente) conduce a una NN que ha aprendido una función computable.

Cerebro humano

Podríamos interpretar el cerebro humano (o cualquier cerebro) como una especie de red neuronal compleja. También podemos hacer la pregunta, si el cerebro humano (modelo) está completo. Ver EG aquí. Esta pregunta es complicada. La intuición diría que podemos realizar cualquier tipo de cálculo, por lo que el cerebro humano está completo. Sin embargo, los argumentos que hemos esbozado aquí muestran que un RNN no está completo. Importante es nuevamente el efecto de memoria. En algún momento, la capacidad de memoria de un cerebro humano no es suficiente para operar con alguna entrada. Por lo tanto, necesitaríamos memoria externa. Entonces, el cerebro humano junto con la memoria externa se completa, obviamente.

Sin embargo, hay un aspecto de la memoria en un cerebro humano que es un poco diferente al de un RNN estándar: puede generalizarse en alto grado, y el mecanismo de direccionamiento para acceder a ciertas activaciones es diferente. Además, tiene algún tipo de pesas adaptativas (que, sin embargo, también solo pueden almacenar información finita).

Answer 8

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

Answer 9

Casi siempre es bueno saber qué clase de la jerarquía de Chomsky es su sistema. Esto es especialmente importante en las clases más restringidas, como los idiomas regulares / autómatas finitos frente a los idiomas sin contexto. También es importante tener la habilidad para reconocer en qué clase es el problema que está tratando de resolver, de lo contrario, uno podría tratar de 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 está completo hace una declaración de que puede construir lo que quiera con él. No dice nada sobre practicidad, solo la posibilidad o imposibilidad de resolver problemas. Esto es dolorosamente cierto cuando se considera que los tarpits de Turing, pero también hay muchos sistemas completos de Turing que se realizan específicamente para fines de nicho que nadie debería soñar con usar para el trabajo general en un entorno de producción.

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

Answer 10

Básicamente significa que con el lenguaje o la arquitectura de programación que están completos
Puede ejecutar una amplia variedad de algoritmos ... sobre todo, cualquier tipo de ellos.

Los idiomas que no son tesor son mucho más estrictos en potencial.

Answer 11

La respuesta es muy simple. Si puede emular una puerta NOR o una NAND con ella, entonces está completo, suponiendo que el resto es solo una cuestión de combinar las cosas juntas.