Que faut-il pour le calcul analogique universel?

Quelles opérations doivent être effectuées pour effectuer un calcul analogique arbitraire ? L'addition, la soustraction, la multiplication et la division seraient-elles suffisantes?

De plus, quelqu'un sait-il exactement quels problèmes peuvent être traités avec le calcul analogique, mais pas avec le numérique?

Malheureusement, il n'y a pas de concept «universel» d'universalité en informatique analogique. Cependant, cet article de Delvenne propose un formalisme unificateur pour l'universalité dans les systèmes dynamiques discrets (par exemple Turing Machines) et continus (par exemple équations différentielles) et passe en revue certains systèmes universels étudiés dans la littérature. Voici un extrait de l'article qui décrit de manière informelle la procédure pour prouver l'universalité d'un système dynamique:

Mais la plupart des systèmes dynamiques étudiés en mathématiques et en physique ont un espace d'état non dénombrable, par exemple, des automates cellulaires, des équations différentielles, des cartes linéaires par morceaux, etc. Des exemples de ces systèmes se sont révélés universels. Leur problème d'arrêt est imité de la machine Turing de la manière suivante. Nous choisissons une famille dénombrable particulière d'états initiaux et une famille dénombrable d'états finaux, ou ensembles finaux d'états. Ensuite, le problème d'arrêt est donné un état initial et un état final / ensemble d'états, si la trajectoire à partir de l'état initial atteindra l'état final / ensemble d'états. Des exemples plus spécifiques sont donnés dans la section 7.

Jean-Charles Delvenne, Qu'est-ce qu'une machine informatique universelle?, Mathématiques appliquées et calcul, volume 215, numéro 4, 15 octobre 2009, pages 1368-1374

Je ne pense pas que la question puisse être résolue à moins que nous ayons une définition du type de calcul dont nous parlons.

L'universalité d'un modèle de machine par rapport à une classe de calcul signifie que tout calcul de cette classe peut être calculé par une machine. À moins que vous ne définissiez la classe des "calculs analogiques arbitraires", nous ne pouvons pas répondre à ce qui leur est universel.

Maintenant, les fonctions que vous avez énumérées ne vous donneront que des polynômes et leur quotient qui est une assez petite classe de fonctions réelles, vous ne pouvez même pas calculer des fonctions simples comme , ⌊ x ⌋ , $2^x$$\lfloor x \rfloor$ , ... en les utilisant.$\sqrt x$

Si votre question est de savoir s'il existe des systèmes physiques qui, à partir d'un état initial, atteindront un autre état dans un certain temps et si cela est toujours calculable, la réponse dépend du type de physique dont nous parlons et de ce que cela signifie de mettre en place. une configuration initiale et l'observation du résultat, etc.

Si nous ne parlons que mathématiquement de la physique classique (nous pouvons définir n'importe quelle configuration initiale avec une précision infinie et sans aucune considération sur des choses comme l'énergie nécessaire pour configurer la configuration et observer le résultat est également du point de vue mathématique), alors il a été connu depuis longtemps qu'il existe des équations différentielles sur les fonctions calculables et leur solution n'est pas calculable, voir Marian B. Pour-El et J. Ian Richards, " Computability in Analysis and Physics ", 1989.

Un cas intéressant est si le problème à n corps est calculable (et si je me souviens bien, la réponse est non, au moins pour ).$n>4$

En règle générale, si nous pouvons simplement vérifier l'égalité de deux nombres réels qui donne une fonction qui n'est pas continue par rapport aux typologies typiques d'informations sur les nombres réels et ne peut donc pas être calculée par une machine de Turing car toute fonction (y compris les fonctions de type supérieur) qu'une machine de Turing peut calculer est continue (par rapport à la topologie des informations).

TL; DR: Si par «ordinateurs analogiques», vous voulez dire des analyseurs différentiels , la réponse est des additionneurs, des unités constantes et un intégrateur. Bournez, Campagnolo, Graça et Hainry ont montré en 2006 ( paywalled / free réimpression ) qu'un modèle idéalisé de celui-ci permet de calculer toutes les fonctions calculables dans le cadre de l' analyse calculable , et ce modèle ne nécessite que ces 3 types d'unités.

Fonctions transcendantales

$\sin$$\exp$$\log$

Modèles informatiques analogiques

Comme souligné par d'autres, le concept de «calcul universel» est moins clair pour les ordinateurs analogiques que pour les ordinateurs standard, où la notion naturelle différente de calculabilité dans différents modèles informatiques était équivalente dans les années 1930 (voir la page Wikipedia sur Church Turing Thesis pour plus de détails ) .

Afin de définir une telle universalité, il faut d'abord définir un bon modèle de calcul analogique, et c'est une tâche difficile, car le modèle doit être idéalisé et suffisamment naturel pour être utile, mais son idéalisation ne doit pas donner un pouvoir irréaliste au modèle. Un exemple d'une si bonne idéalisation est le ruban infini des machines de Turing. Le problème avec les ordinateurs analogiques vient avec des nombres réels qui pourraient permettre de construire des trucs déraisonnables comme la machine Zeno . Cependant, plusieurs de ces modèles ont été proposés et utilisés dans la littérature (Le GPAC est le sujet principal de cette réponse, mais j'essaie d'être complet dans la liste ci-dessous, sans hypercalculateur ):

• l' ordinateur analogique à usage général (GPAC), défini par Claude E.Shannon en 1941 ( pdf payant ) pour modéliser les analyseurs différentiels . La définition du GPAC a récemment été affinée et sa puissance de calcul a été revue à la hausse;
• la machine Blum-Shub-Smale , qui agit à des moments discrets sur des nombres réels. Il est étroitement lié au modèle Real RAM souvent utilisé en géométrie computationnelle;
• $\mathbb R$
• Réseaux de neurones ;
• Analyse calculable , qui examine les nombres réels calculables par une machine de Turing.

Puissance du modèle GPAC

$\Gamma$$\zeta$$y(t)=\Gamma(t)$Il a longtemps semblé qu'un tel ordinateur analogique n'était pas «universel», car il ne pouvait pas générer de fonctions calculables raisonnables, utilisées par les mathématiciens.

$f$$y(t)$$f(x)$$x$$\gamma$$\zeta$.

Bournez, Graça et Pouly ont ensuite montré en 2013 que ces ordinateurs analogiques peuvent simuler efficacement une machine de Turing ( p.181 d'un gros pdf ) et, en 2014, que les classes de complexité P et NP sont équivalentes dans ce modèle.

Serait-il utile de proposer qu'un système analogique universel puisse être modélisé par un réseau neuronal infini, c'est-à-dire que toute autre valeur d'entrée / sortie du système analogique puisse être répliquée sur un réseau neuronal adapté pour une opération donnée, et les opérations peuvent être enchaînées selon les besoins?

Bien que j'aie formulé cette idée par moi-même, une recherche ultérieure a montré une proposition similaire:

Ce qui émerge est une thèse de type Church-Turing, appliquée au domaine du calcul analogique, qui présente le modèle de réseau neuronal à la place de la machine numérique de Turing (voir ici ).

Sans doute, alors tout ce dont vous auriez besoin serait les opérations primitives pour déplacer la valeur d'un nœud à un autre. Sur le brassard qui pourrait être plus, moins et diviser pour obtenir le rapport entre les connexions.

Maintenant, en ce qui concerne les problèmes insolubles, regardez où les réseaux de neurones ont été appliqués avec succès ou sont sous-performants en raison de leur implémentation sur un ordinateur discret.

(et je m'excuse si mon point de vue presque profane sur ce sujet est clairement évident)