Tesis de Church-Turing y poder computacional de redes neuronales

La tesis de Church-Turing establece que todo lo que se puede calcular físicamente, se puede calcular en una máquina de Turing. El documento "Computación analógica a través de redes neuronales" (Siegelmannn y Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) afirma que una red neuronal de cierta forma (la configuración se presenta en el documento) es más poderosa. Los autores dicen que, en un tiempo exponencial, su modelo puede reconocer lenguajes que no son computables en el modelo de máquina de Turing.

¿No contradice esto la tesis de la Iglesia-Turing?

No, todavía es consistente con la tesis de Church-Turing, su modelo viene equipado con números reales reales (como en los elementos arbitrarios de ), que casi inmediatamente extiende el poder más allá del de una máquina de Turing. De hecho, el título de 1.2.2 es "El significado del peso real (no computable)", donde discuten por qué su modelo está construido para incluir componentes no computables.$\mathbb{R}$

De hecho, hay muchos modelos de cómputo que exceden el poder de las máquinas de Turing (qv hipercomputación ). El problema es que ninguno de estos aparentemente puede construirse en el mundo real (pero tal vez en el mundo , lo siento, no pude resistir).$\mathbb{R}$

Para ampliar un poco la respuesta de Luke , construir físicamente una red neuronal para resolver cualquier lenguaje requiere producir componentes electrónicos con resistencias infinitamente precisas, etc. Esto no es posible, de múltiples maneras:

1. No puedes producir una resistencia de exactamente .$\mathrm{2\,\Omega}$

2. La resistencia cambia con la temperatura y la corriente que fluye a través de la resistencia cambiará su temperatura.

3. Incluso suponiendo que conozca a un ingeniero / hechicero electrónico que pueda producir resistencias a cualquier valor exacto que elija y que no cambie la resistencia con la temperatura, configurar su máquina para decidir un lenguaje inconfundible requerirá valores de resistencia inconfundibles. Por lo tanto, no hay forma de que pueda decirle a su ingeniero / brujo electrónico qué valor de resistencia necesita.

Entonces, aunque, en principio, estas máquinas pueden decidir cualquier idioma, no violan Church-Turing porque no pueden construirse físicamente.

Es posible que desee participar en algunas reglas de abogacía y afirmar que alguien podría entregarle una de estas máquinas y decir: "Oye, mira, ¡esta máquina tiene exactamente los valores de resistencia correctos para resolver el problema de detención!" Sin embargo, no tienen forma de probar esta afirmación, ya que no pueden medir los componentes con una precisión infinita, por lo que lo mejor que pueden reclamar con justificación es "Probé esto en un conjunto finito de entradas y resolvió correctamente el problema de detención en esas entradas ". Bueno, cualquier subconjunto finito del problema de detención ya es decidible por Turing, así que eso no es nada emocionante.