Thèse de Church-Turing et puissance de calcul des réseaux de neurones

La thèse de Church-Turing déclare que tout ce qui peut être physiquement calculé, peut être calculé sur une machine de Turing. L'article «Analog computation via neural networks» (Siegelmannn et Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) affirme qu'un réseau neuronal d'une certaine forme (les paramètres sont présentés dans l'article) est plus puissant. Les auteurs disent que, dans un temps exponentiel, leur modèle peut reconnaître des langages qui ne sont pas calculables dans le modèle de la machine de Turing.

Cela ne contredit-il pas la thèse de Church-Turing?

Non, il est toujours cohérent avec la thèse de Church-Turing, leur modèle est équipé de vrais nombres réels (comme dans les éléments arbitraires de ), ce qui étend à peu près immédiatement la puissance au-delà de celle d'une machine de Turing. En fait, le titre du 1.2.2 est "La signification du poids réel (non calculable)", où ils expliquent pourquoi leur modèle est conçu pour inclure des composants non calculables.$\mathbb{R}$

Il existe en effet de nombreux modèles de calcul qui dépassent la puissance des machines de Turing (qv Hypercomputation ). Le hic, c'est qu'aucun de ceux-ci ne peut apparemment être construit dans le monde réel (mais peut-être dans le monde - désolé, je n'ai pas pu résister).$\mathbb{R}$

Pour développer un peu la réponse de Luke , la construction physique d'un réseau neuronal pour résoudre n'importe quel langage nécessite la production de composants électroniques avec des résistances infiniment précises et ainsi de suite. Ce n'est pas possible, de plusieurs façons:

1. Vous ne pouvez pas produire une résistance d'exactement .$\mathrm{2\,\Omega}$

2. La résistance change avec la température et le courant traversant la résistance changera sa température.

3. Même en supposant que vous connaissiez un ingénieur / sorcier électronique qui peut produire des résistances à la valeur exacte que vous choisissez et qui ne changent pas la résistance avec la température, configurer votre machine pour décider d'un langage non calculable nécessitera des valeurs de résistance non calculables. Il n'y a donc aucun moyen de dire à votre ingénieur / sorcier électronique la valeur de résistance dont vous avez besoin.

Ainsi, bien que, en principe, ces machines puissent décider de n'importe quelle langue, elles ne violent pas Church-Turing parce qu'elles ne peuvent pas être construites physiquement.

Vous voudrez peut-être vous engager dans des règles de droit et prétendre que quelqu'un pourrait vous remettre une de ces machines et dire: "Hé, regardez, cette machine a justement exactement les bonnes valeurs de résistance pour résoudre le problème d'arrêt!" Cependant, ils n'ont aucun moyen de prouver cette affirmation, car ils ne peuvent pas mesurer les composants avec une précision infinie, donc le mieux qu'ils peuvent affirmer avec justification est "J'ai testé cela sur un ensemble fini d'entrées et il a correctement décidé le problème d'arrêt sur ces entrées. " Eh bien, tout sous-ensemble fini du problème d'arrêt est déjà décidable par Turing, donc ce n'est rien d'excitant.