Quelle est l'utilité Turing-complet? sont les réseaux de neurones Türing complète?

Question

Lors de la lecture des documents sur l'intégralité des réseaux de neurones Turing récurrents:, j'ai eu le sentiment que la preuve qui a été donné il y avait (par exemple avec la calculabilité Turing les réseaux de neurones, Hava T. Siegelmann et Eduardo D. Sontag, 1991) pas vraiment pratique. Par exemple, le papier référencé a besoin d'un réseau de neurones dont l'activité des neurones doit être de rigueur à l'infini (pour représenter fiable un nombre rationnel). D'autres preuves ont besoin d'un réseau de neurones de taille infinie. De toute évidence, ce n'est pas vraiment pratique.

Mais je commençais à me demander maintenant si elle ne du sens du tout pour demander Turing-complet. Par la définition stricte, aucun système informatique est complet de nos jours parce Turing qu'aucun d'entre eux sera en mesure de simuler la bande infinie.

Il est intéressant de feuilles de spécification de langage de programmation le plus souvent ouverts si elles sont ou non Türing complète. Tout cela se résume à la question si elles seront toujours en mesure d'allouer plus de mémoire et si la taille de l'appel de fonction est infinie. La plupart des spécifications ne précise pas vraiment. Bien sûr, toutes les implémentations disponibles sont ici limitées, toutes les implémentations pratiques des langages de programmation ne sont pas complète Turing.

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

Et cela me amène à la question suivante: Quelle est l'utilité du terme complet Turing du tout

?

Retour aux réseaux neuronaux: Pour toute mise en œuvre pratique d'un réseau de neurones (y compris notre propre cerveau), ils ne seront pas en mesure de représenter un nombre infini d'états, soit par la définition stricte de Turing-complet, ils ne sont pas Turing Achevée. Il en va de la question si les réseaux de neurones sont Turing son sens de faire du tout?

La question s'ils sont aussi puissants que les machines à états finis a déjà répondu à beaucoup plus tôt (1954 par Minsky, la réponse est évidemment: oui) et semble aussi plus facile de répondre. À savoir, au moins en théorie, qui était déjà la preuve qu'ils sont aussi puissants que tout ordinateur.

---

D'autres questions sont plus sur ce que je veux vraiment savoir:

• Y at-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 mises en œuvre pratiques des réseaux de neurones avec des ordinateurs? (Turing-complétude ne sont pas utiles comme argumenté ci-dessus.)

Answer 1

Le point de dire qu'un modèle mathématique Turing complet est de révéler la capacité du modèle à effectuer tout calcul, donné une quantité de ressources suffisantes (c.-à-infini) , ne pas montrer si une la mise en œuvre spécifique d'un modèle ne possède ces ressources. modèles complets non-Turing ne serait pas en mesure de gérer un ensemble spécifique de calculs, même avec des ressources assez , ce qui révèle une différence dans la façon dont les deux modèles fonctionnent, même quand ils ont limité ressources . Bien sûr, prouver cette propriété, vous devez faire assumer que les modèles sont capables d'utiliser une quantité infinie de ressources, mais cette propriété d'un modèle est encore pertinent lorsque les ressources sont limité.

Answer 2

Turing-complétude des réseaux de neurones récurrents pourrait signifier: les tables de transition (finie) de chaque machine de Turing (avec une longueur d'état fini et un ruban infini) peut être modélisé par un réseau neuronal récurrent finie (un nombre fini de neurones avec de nombreux Etats, finiment en particulier que deux états). Les tables de transition définissent trois fonctions:

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

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

• direction (à l'état actuel, symbole courant)

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

Les neurones verts lire le symbole dans la cellule courante (en représentation binaire), les neurones gris (initally muets) déterminent l'état actuel, les neurones rouges écrivent le nouveau symbole de la cellule actuelle, les neurones jaunes déterminer si d'aller gauche ou droite. Les neurones bleus sont les neurones internes (d'abord muet).

La revendication est, pour chaque machine de Turing il y a un tel 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.

Answer 3

Quand les ordinateurs modernes sont dits complet Turing il y a une exception non-dit pour le dispositif de stockage infini décrit Turing, ce qui est évidemment un impossibilty sur un dispositif de calcul physique fini. Si un dispositif de calcul peut tout faire une machine de Turing peut faire (stockage infini NONOBSTANT) est complet Turing pour toutes fins pratiques. Par cette définition moins stricte de complet Turing , oui, il est possible que de nombreux réseaux de neurones sont complet Turing .

Il est bien sûr possible de créer un qui est pas complet Turing .

Answer 4

Pour répondre en partie à votre deuxième question:

Réseaux de Neurones ont la propriété d'être approximateurs universel - c'est, ils peut approximer une fonction à un degré quelconque de précision. Il est la partie « degré de précision » qui maintient le réseau de neurones du besoin d'être infini.

Answer 5

Réseaux de neurones régulier anticipatifs sont pas turing complet . Ils sont, en effet, ce qui équivaut à une seule fonction mathématique complexe qui peut faire beaucoup de calculs, mais n'a pas de capacité en boucle ou d'autres accomplir un opérations de contrôle de flux.

Cependant, si vous câbler un réseau de neurones avec un moyen d'accéder à un environnement stateful il peut être être transformé en une machine complète turing .

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

• l'entrée du réseau de neurones est la valeur de la bande et l'état précédent
• la sortie du réseau de neurones est l'état suivant et l'action

Vous pouvez ensuite former le réseau de neurones à imiter les actions d'une table d'état de machine de Turing souhaitée / configuration (peut-être par l'apprentissage supervisé sur les actions d'une autre machine de Turing?)

Note: L'idée de courir un filet à plusieurs reprises avec anticipatrice une certaine forme de retour d'état est essentiellement équivalent à un réseau de neurones récurrent . Ainsi, vous pouvez penser à un réseau de neurones récurrent plus la logique qui l'exécute à plusieurs reprises comme étant complète Turing. Vous avez besoin de la logique supplémentaire (au-delà du réseau lui-même) pour assurer l'exhaustivité, car il est Turing nécessaire de gérer les choses comme la fin, la répétition et IO.

Answer 6

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

Au contraire, il but de dire si une langue est capable d'exprimer une tâche particulière. C'est, je dirais que c'est vraiment exprimant un algorithme non effectuer il.

Les réseaux de neurones ne sont pas une langue, il est une question d'exprimer un algorithme en termes d'un réseau de neurones, plutôt que la capacité de ce réseau. Je ne sais pas la réponse à la dernière partie de votre question!

Answer 7

Après de nombreuses années, permettez-moi de donner une réponse à cette question moi-même.

complet Turing

• Aussi puissant qu'une machine de Turing (TM).
• nécessite un infini mémoire . C'est à dire. dans la pratique, aucun appareil physique jamais peut être complet Turing.
• Soit un ordinateur personnel normal (PC) :
  • Une instance physique spécifique est pas complet Turing , car il a une mémoire finie.
  • Cependant, tenez compte des concept de PC comme quelque chose où vous pouvez ajouter de la mémoire à la demande. Tous les programmes continueront à fonctionner de la même manière lorsque vous ajoutez plus de mémoire. Pour toute entrée donnée, et un programme donné, il y a une quantité maximale de mémoire telle qu'elle devrait fonctionner. (Ne soyons pas pédant maintenant de la limite d'adresse mémoire int64 ou des choses comme ça. Ce sont des limites techniques qui pourraient être résolus, par exemple par de grands ints, etc.) Ainsi, nous pouvons dire que le concept de un PC est complète Turing .
• est vraiment complet Turing principalement sur le concept de mémoire. Considérons une machine à états finis / automate (FSA), et un certain accès à la mémoire externe. En fonction du type de mémoire, vous vous retrouvez dans les différentes classes de la hiérarchie Chomsky:
  • pas de mémoire / mémoire finie: langues régulières
  • simple pile: pushdown automates, langues sans contexte
  • deux ou plusieurs piles: complet Turing, récursive langue dénombrable

récurrent réseaux de neurones (RNN)

Sur la puissance de calcul des réseaux de neurones

Un document souvent cité est Sur la puissance de calcul des réseaux de neurones, Siegelmann & Sonntag, 1992 , qui stipule que RNNs sont complets Turing. Ce document suppose que nous avons des nombres rationnels sans limites dans le numérateur / dénominateur, à savoir la mémoire infinie est codé en tant que nombres rationnels ou des nombres à virgule flottante de précision infinie. Voir aussi . En général, nous ne modélisons pas NN d'une manière qui est fonctionne avec des nombres rationnels (sans limite). Lorsque nous nous limitons à (R) avec des poids de NNs précision finie et activations, la preuve dans le papier tombe appart, et ne s'applique plus. Ainsi, cet article est pas pertinent.

Il y a un article plus récent, sur la puissance de calcul pratique de précision finis RNNs pour la langue de reconnaissance, Weiss et al 2018 , qui traite exactement cela.

approximator Universal

Il est bien connu que la plupart des réseaux neuronaux standards sont approximateurs universel . Cet article stipule que toute fonction donnée (non constante, bornée et continue), et donné un certain seuil autorisé, vous pouvez construire un NN qui se rapproche de cette fonction dans le seuil autorisé. Il s'agit des espaces vectoriels de dimension finie. Quand on parle de calculabilité, nous parler de séquences, nous avons donc un espace vectoriel de dimension infinie. Ainsi, cette propriété est pas pertinente.

Sans mémoire externe

Ainsi, pour indiquer explicitement: Sans mémoire externe, la norme RNN, et aussi LSTM est pas complète Turing . Il y a aussi pas de moyen straight-forward comment vous pouvez définir un concept de RNN , où l'on pouvait ajouter de la mémoire à la demande. La mémoire d'un RNN sont les plus récentes activations cachés. Ajouter d'autres moyens de mémoire pour modifier le NN, à savoir \ ajoutant de nouveaux neurones, ajoutant ainsi le fonctionnement interne de celui-ci. Ceci est comme changer le programme lui-même.

Avec mémoire externe

Il est Machine Neural Turing (NTM) et quelques modèles similaires, qui ont une sorte de mémoire externe. Ici, il est de penser straight-forward sur une concept de NTM où vous ajouter de la mémoire à la demande. Ainsi, nous pouvons dire que concept de NTM est Türing complet .

Il y a quelques détails comme le type de soins utilisés dans les têtes, qui a besoin d'une certaine adaptation. Il y a un suivi sur le modèle, le Différentiable ordinateur neuronal (DNC) qui traite explicitement , et dispose également d'un mécanisme explicite à ajouter de la mémoire.

Apprentissage / formation

Nous avons parlé surtout de la puissance de calcul théorique. Une question très différente est de savoir si le NN peut apprendre une telle fonction. C'est à dire. si la formation (recherche de gradient) conduit à un NN qui a appris une fonction récursive.

cerveau humain

Nous pourrions interpréter le cerveau humain (ou tout cerveau) comme une sorte d'un réseau de neurones complexe. Nous pouvons aussi poser la question, si le cerveau humain (modèle) est complet Turing. Voir par exemple ici . Cette question est une question délicate. L'intuition dirait que nous sommes en mesure d'effectuer tout type de calcul, donc le cerveau humain est complet Turing. Cependant, les arguments que nous avons décrit ici montre qu'un RNN ne Türing complète. L'important est de nouveau l'effet mémoire. À un moment donné, la capacité mémoire d'un cerveau humain ne suffit pas de fonctionner sur une entrée. Ainsi, nous aurions besoin de mémoire externe. Ainsi, le cerveau humain en même temps que la mémoire externe est complète Turing, évidemment.

Cependant, il y a un aspect de la mémoire dans un cerveau humain qui est un autre bit que dans un RNN standard: Il peut se généralisent à un haut degré, et le mécanisme d'adressage d'accéder à certaines activations est différent. En outre, il a une sorte de poids adaptatifs (qui cependant ne peut également stocker des informations fini).

Answer 8

Je pense un point important sur la machine de Turing est que pour tout donnée entrée et programme, la machine seulement besoin d'une quantité finie de bande, en supposant qu'il arrête un peu de temps. Voilà pourquoi je dirais que le terme « Türing complet » est utile: Vous avez seulement besoin mémoire finie pour exécuter un programme complet spécifique turing sur une entrée spécifique (si les arrêts du programme). Mais si vous avez une machine / langue / technologie complète non-turing, il ne sera pas en mesure de simuler certains algorithmes, peu importe la quantité de mémoire que vous ajoutez.

Answer 9

Il est presque toujours agréable de savoir quelle classe dans la hiérarchie est votre système Chomsky. Ceci est particulièrement important dans les classes plus resserrées, comme les langages réguliers / automates finis vs langues sans contexte. De plus ayant la compétence pour reconnaître quelle classe votre problème que vous essayez de résoudre est en est aussi important, sinon on pourrait essayer de faire des choses stupides comme l'analyse syntaxique HTML ou XML avec des expressions régulières seulement, ce qui est impossible.

Avoir la knowlegde que votre formalisme ou le système complet Türing marques une déclaration que vous pouvez construire tout ce que vous voulez. Il ne dit rien au sujet de l'aspect pratique, juste la possibilité ou l'impossibilité de résoudre les problèmes. Ceci est douloureusement vrai lorsque l'on considère turing tarpits, mais il y a aussi beaucoup de systèmes complets turation qui sont spécifiquement conçus à des fins de niche que personne ne devrait jamais rêver d'utiliser pour le travail d'usage général dans un contexte de production.

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

Answer 10

Fondamentalement, cela signifie que le langage de programmation ou de l'architecture qui complète
Turing vous pouvez exécuter grande variété d'algorithmes ... la plupart du temps -. tout type d'entre eux

Les langues non sont beaucoup plus strictes de Turing potentiel.

Answer 11

La réponse est très simple. Si vous pouvez émuler un NOR ou une porte NON-ET avec elle, il est complet Turing, en supposant que le reste est juste une question de combiner les choses ensemble.