Quelle est l’utilité de Turing? les réseaux de neurones sont-ils complets?

En lisant certains articles sur la complétude de Turing des réseaux neuronaux récurrents (par exemple: calculabilité de Turing avec les réseaux neuronaux, Hava T. Siegelmann et Eduardo D. Sontag, 1991), j’ai eu l’impression que la preuve pratique. Par exemple, le papier référencé a besoin d’un réseau neuronal dont l’activité neuronale doit être d’une exactitude infinie (pour être fiable, représenter un nombre rationnel quelconque). D’autres preuves nécessitent un réseau neuronal de taille infinie. Clairement, ce n’est pas vraiment si pratique.

Mais j’ai commencé à me demander maintenant si cela avait du sens de demander la complétude de Turing. Par définition ssortingcte, aucun système informatique n’est à l’heure actuelle complet, car aucun d’entre eux ne pourra simuler la bande infinie.

Il est intéressant de noter que la spécification du langage de programmation le laisse le plus souvent ouvert s’il est complet ou non. Tout se résume à la question de savoir s’ils pourront toujours allouer plus de mémoire et si la taille de la stack des appels de fonction est infinie. La plupart des spécifications ne spécifient pas vraiment cela. Bien sûr, toutes les implémentations disponibles sont limitées ici, donc toutes les implémentations pratiques des langages de programmation ne sont pas complètes.

Donc, ce que vous pouvez dire, c’est que tous les systèmes informatiques sont tout aussi puissants que les machines à états finis et pas plus.

Et cela m’amène à la question suivante: à quel point le terme Turing est-il utile?

Et retour aux réseaux neuronaux: Pour toute implémentation pratique d’un réseau neuronal (y compris notre propre cerveau), ils ne pourront pas représenter un nombre infini d’états, c’est-à-dire qu’ils ne seront pas complets. La question de savoir si les réseaux neuronaux sont complets est-elle logique?

La question de savoir si elles sont aussi puissantes que les machines à états finis a déjà été traitée beaucoup plus tôt (1954 par Minsky, la réponse bien sûr: oui) et semble également plus facile à répondre. C’est à dire, du moins en théorie, que c’était déjà la preuve qu’ils sont aussi puissants que n’importe quel ordinateur.


Quelques autres questions qui concernent plus ce que je veux vraiment savoir:

  • Y a-t-il un terme théorique qui peut dire quelque chose de plus précis sur la puissance de calcul d’un ordinateur? (compte tenu de son espace mémoire limité)

  • Comment pouvez-vous comparer la puissance de calcul des implémentations pratiques des réseaux neuronaux avec les ordinateurs? (Turing-complete n’est pas utile comme argumenté ci-dessus.)

    Le fait de dire qu’un modèle mathématique est Turing Complete a pour objective de révéler la capacité du modèle à effectuer des calculs, avec une quantité suffisante de ressources (infinie) , sans indiquer si une implémentation spécifique d’un modèle possède ces ressources. Les modèles complets non Turing ne seraient pas en mesure de gérer un ensemble spécifique de calculs, même avec des ressources suffisantes , ce qui révèle une différence dans la manière dont les deux modèles fonctionnent, même lorsqu’ils disposent de ressources limitées . Bien sûr, pour prouver cette propriété, il faut supposer que les modèles peuvent utiliser une quantité infinie de ressources, mais cette propriété d’un modèle est pertinente même lorsque les ressources sont limitées.

    Turing-exhaustivité des réseaux neuronaux récurrents pourrait signifier: les tables de transition (finies) de chaque machine de Turing (avec une tête à états finis et une bande infinie) peuvent être modélisées par un réseau neuronal récurrent fini (beaucoup de neurones États, en particulier seulement deux États). Les tableaux de transition définissent trois fonctions:

    • état suivant (état actuel, symbole actuel)

    • symbole suivant (état actuel, symbole actuel)

    • direction (état actuel, symbole actuel)

    Voici comment un réseau neuronal récurrent peut effectuer cette tâche (juste une esquisse très brute):

    entrer la description de l'image ici

    Les neurones verts lisent le symbole dans la cellule actuelle (en représentation binary), les neurones gris (muet au début) déterminent l’état actuel, les neurones rouges écrivent le nouveau symbole dans la cellule en cours, les neurones jaunes déterminent s’il faut aller à gauche ou à droite . Les neurones bleus sont les neurones internes (initialement muets).

    L’affirmation est que, pour chaque machine Turing, il existe un réseau neuronal récurrent.

    Je me demande s’il existe un moyen systématique de construire un tel réseau à partir de tables de transition données.

    Lorsque les ordinateurs modernes sont dits Turing Complete, il existe une exception tacite pour le périphérique de stockage infini décrit par Turing, qui est évidemment une impossibilité sur un périphérique de calcul physique fini. Si un appareil de calcul peut faire tout ce qu’une machine de Turing peut faire (stockage illimité malgré tout), il est complet pour toutes les fins pratiques. Par cette définition moins ssortingcte de la complétude de Turing , oui, il est possible que de nombreux réseaux de neurones soient complets .

    Il est bien sûr possible d’en créer un qui ne soit pas complet .

    Pour répondre partiellement à votre deuxième question:

    Les réseaux de neurones ont la propriété d’être des approximateurs universels – c’est-à-dire qu’ils peuvent approcher n’importe quelle fonction avec un degré de précision arbitraire. C’est la partie “degré de précision” qui empêche le réseau neuronal d’être infini.

    Les réseaux neuronaux d’anticipation réguliers ne sont pas complets . Ils sont, en effet, équivalents à une fonction mathématique complexe qui peut faire pas mal de calculs mais n’a aucune capacité à effectuer des opérations de bouclage ou d’autres opérations de contrôle.

    Cependant, si vous connectez un réseau neuronal avec un moyen d’accéder à un environnement dynamic, vous pouvez le transformer en une machine complète .

    Comme exemple le plus sortingvial, vous pouvez recréer une machine de Turing de style classique où:

    • l’entrée dans le réseau neuronal est la valeur sur la bande et l’état précédent
    • la sortie du neural network est le prochain état et l’action

    Vous pouvez ensuite entraîner le réseau neuronal à émuler les actions de n’importe quelle table / configuration d’état de machine de turing souhaitée (peut-être par apprentissage supervisé sur les actions d’une autre machine de turing?)

    Note: L’idée d’exécuter un réseau d’anticipation avec une forme de retour d’état est essentiellement équivalente à un réseau neuronal récurrent . Ainsi, vous pouvez penser à un réseau neuronal récurrent et à la logique qui le fait fonctionner à plusieurs resockets, étant donné que Turing est terminé. Vous avez besoin de la logique supplémentaire (au-delà du réseau lui-même) pour garantir l’exhaustivité de Turing, car il est nécessaire de gérer des éléments tels que la terminaison, la répétition et les E / S.

    Je pense que le concept de complétude de Turing ne vise pas à nous dire si un ordinateur particulier peut effectuer une tâche particulière.

    Il s’agit plutôt de savoir si une langue particulière est capable d’exprimer une tâche particulière. C’est-à-dire que je dirais qu’il s’agit vraiment d’ exprimer un algorithme qui ne l’ exécute pas.

    Comme les réseaux de neurones n’ont pas de langage, il s’agit d’exprimer un algorithme en termes de neural network, plutôt que la capacité de ce réseau. Je ne connais donc pas la réponse à la dernière partie de votre question!

    Je pense qu’un point important à propos de la machine à turing est que pour une entrée et un programme donnés , la machine n’aura besoin que d’une quantité limitée de bande, en supposant qu’elle s’arrête un certain temps. C’est pourquoi je dirais que le terme “turing complete” est utile: vous n’avez besoin que d’une mémoire finie pour exécuter un programme complet spécifique sur une entrée spécifique (si le programme s’arrête). Mais si vous avez une machine / un langage / une technologie non complète, elle ne pourra pas simuler certains algorithmes, quelle que soit la quantité de mémoire que vous ajoutez.

    Il est presque toujours agréable de savoir quelle classe de la hiérarchie de Chomsky est votre système. Ceci est particulièrement important dans les classes les plus restreintes, comme les langages réguliers / automates finis et les langages sans contexte. Avoir la capacité de reconnaître la classe dans laquelle le problème que vous essayez de résoudre est également important, sinon on pourrait essayer de faire des choses idiotes comme parsingr HTML ou XML avec des expressions régulières uniquement, ce qui est impossible.

    Avoir le savoir-faire que votre formalisme ou votre système est en train de faire est une déclaration que vous pouvez créer ce que vous voulez avec. Il ne dit rien sur l’aspect pratique, mais sur la possibilité ou l’impossibilité de résoudre des problèmes. C’est douloureusement vrai lorsque l’on considère les bâches, mais il existe également de nombreux systèmes complets conçus spécifiquement pour des besoins spécifiques que personne ne devrait jamais imaginer pour des travaux généraux dans un environnement de production.

    En bref, une bonne connaissance de la hiérarchie de Chomsky vous aidera dans de très nombreuses situations, et pas seulement pour choisir le bon type d’parsingur; regexp, pushdown, CFG ou plus puissant, mais aussi pour choisir le bon type de machine ou de formalisme pour exprimer des processus en général.

    Fondamentalement, cela signifie qu’avec un langage de programmation ou une architecture complète, Turing est complet
    vous pouvez exécuter une grande variété d’algorithmes … principalement – n’importe quel type.

    Les langages non-Turing ont un potentiel beaucoup plus important.

    La réponse est très simple. Si vous pouvez émuler une porte NOR ou une porte NAND, alors il s’agit de Turing Complete, en supposant que le rest consiste simplement à combiner les choses ensemble.