dans quelle mesure Turing est-il complet? les réseaux de neurones sont-ils complets?

Question

Lors de la lecture de certains articles sur les Turing de l'exhaustivité de neurones récurrents filets (par exemple: Turing compilation avec des réseaux de neurones, Hava T. Siegelmann et Eduardo D. Sontag, 1991), j'ai eu le sentiment que la preuve qui a été donné, il n'était pas vraiment pratique. Par exemple référencés papier a besoin d'un réseau de neurones dont l'activité des neurones doit être de l'infini exactitude (à la fiabilité de représenter tout nombre rationnel). D'autres preuves ont besoin d'un réseau de neurones de taille infinie. Clairement, ce n'est pas vraiment pratique.

Mais j'ai commencé à me demander aujourd'hui si ce n'est faire du sens à demander de Turing complet. Par la définition stricte, pas de système informatique d'aujourd'hui est Turing complet, car aucun d'entre eux sera en mesure de simuler l'infini de bande.

Fait intéressant, le langage de programmation spécification des feuilles le plus souvent ouverts si elles sont turing ou pas. Tout se résume à la question de savoir si ils seront toujours en mesure d'allouer plus de mémoire et si l'appel de la fonction taille de la pile est infini. La plupart des spécifications n'ont pas vraiment le préciser. Bien sûr, toutes les implémentations disponibles sont limitées, de sorte que tous les implémentations pratiques des langages de programmation ne sont pas Turing.

Donc, ce qu'on peut dire, c'est que tous les systèmes informatiques sont tout aussi puissants que des machines à états finis, et pas plus.

Et cela m'amène à la question suivante: Quelle est l'utilité de la durée de Turing complet à tous?

Et à l'arrière pour les réseaux de neurones: Pour toute mise en œuvre pratique d'un réseau neuronal (y compris notre propre cerveau), ils ne seront pas en mesure de représenter un nombre infini d'états, c'est à dire par la définition stricte de Turing à l'exhaustivité, ils ne sont pas Turing. Le fait de la question de savoir si les réseaux de neurones sont Turing avoir un sens à tout?

La question de savoir si ils sont aussi puissants que des machines à états finis a été déjà répondu beaucoup plus tôt (1954 par Minsky, la réponse de cours: oui) et semble également plus facile de répondre. I. e., en théorie du moins, c'était déjà la preuve qu'ils sont aussi puissants que n'importe quel ordinateur.

---

Quelques autres questions qui sont plus au sujet de ce que je veux vraiment savoir:

• Est-il théorique terme qui peut dire quelque chose de plus spécifique à propos de la puissance de calcul d'un ordinateur? (compte tenu de sa faible espace mémoire)

• Comment pouvez-vous comparer la puissance de calcul de pratique, implémentations de réseaux de neurones avec des ordinateurs? (Turing-complétude n'est pas utile comme raisonnée ci-dessus).

Answer 1

Le point de en précisant qu'un modèle mathématique Turing est de révéler la capacité du modèle à effectuer tout calcul, étant donné une quantité suffisante de ressources (c'est à dire à l'infini), de ne pas le montrer sur l'opportunité de la mise en œuvre d'un modèle de ces ressources. Non Turing modèles ne seraient pas en mesure de gérer un ensemble spécifique de calculs, même avec suffisamment de ressources, de quelque chose qui révèle une différence dans la façon dont les deux modèles fonctionnent, même quand ils ont des ressources limitées. Bien sûr, pour prouver cette propriété, que vous avez à faire présumer que les modèles sont en mesure d'utiliser une quantité infinie de ressources, mais cette propriété d'un modèle est pertinent, même lorsque les ressources sont limitées.

Answer 2

Lorsque les ordinateurs modernes sont dit être Turing il y a un non-dits d'exception pour l'infini périphérique de stockage de Turing décrit, qui est évidemment une impossibilité sur une durée de physique de calcul. Si un calcul appareil peut faire tout ce qu'une machine de Turing peut faire (stockage infini de ne pas résister), il est Turing complet pour toutes fins utiles. Par ce moins stricte définition de Turing à l'exhaustivité, oui, il est possible que de nombreux réseaux de neurones sont de tournage complète.

Il est bien sûr possible d'en créer un qui n'est pas Turing.

Answer 3

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 approximer 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.

Answer 4

Je pense que le concept de Turing à l'exhaustivité n'est pas prévu pour nous dire si un ordinateur particulier peut effectuer une tâche particulière.

Plutôt, c'fins de déterminer si une langue est capable d'exprimer une tâche particulière. C'est, je dirais, c'est vraiment exprimer un algorithme de ne pas effectuer il.

Que les réseaux de neurones n'ont pas une langue, c'est une question d'exprimer un algorithme en termes de réseau de neurones, plutôt que de la capacité de ce réseau. Donc je ne sais pas la réponse à la dernière partie de votre question!

Answer 5

Je pense que d'un point important à propos de la machine de turing est que pour toute donnée d'entrée et de programme, la machine seulement besoin d'une quantité finie de la bande, en supposant qu'il s'arrête quelque temps. C'est pourquoi je dirais que le terme "turing complet" est utile: il Vous suffit finis de mémoire pour exécuter une fonction spécifique de turing programme complet sur certains points spécifiques de l'entrée (si le programme s'arrête). Mais si vous avez un non-turing-complet de la machine/la langue/de la technologie, il ne sera pas en mesure de simuler certains de ces algorithmes, pas d'importance combien vous ajoutez de mémoire.