Machine de turing

[invite251213]

Bonjour.

J'espère avant tout que je poste dans le bon forum, mais ma question risque de ne pas trop recevoir de réponses dans les forums d'informatique...j'ai préféré poster dans la partie la plus "générale du forum"

Avant l'invention des ordinateurs numériques, il existait des machines à calculer qui utilisaient des grandeurs analogiques dans leurs calculs (parfois fabriquées avec des AOP).

Très peu programmables, elles permettaient de faire des dérivées et des intégrations, ce que nos ordinateurs numériques ne permettaient pas.

D'où ma première question : pourquoi nos PC numériques ne peuvent-ils pas faire de calcul infinitésimal-analytique ?

Seulement, par définition, nos ordinateurs numériques sont équivalents à des machines de Turing.
Que les calculateurs analogiques puissent faire des trucs impossibles à faire par un truc équivalent à une machine de Turing signifierait que ces calculateurs ne seraient pas des machines de Turing !

D'où ma question : est-ce que ces calculateurs analogiques sont équivalents aux machines de Turing ?

Et dans le cas des ordinateurs quantiques ?

Comment peut-on prouver que nos PC quantiques et/ou analogiques sont ou ne sont pas équivalents aux machines de Turing ?
-----

[invite9ac7aecb]

pourquoi nos PC numériques ne peuvent-ils pas faire de calcul infinitésimal-analytique ?

Je ne comprends pas, maple et mathematica (entre autres) calculent très bien des intégrales ou des dérivées. Non?

[invite251213]

Je ne comprends pas, maple et mathematica (entre autres) calculent très bien des intégrales ou des dérivées. Non?

Sans utiliser d'approximations ?

Parce que visiblement, il me semble que les algorithmes qui permettent de calculer des dérivée ou des intégrales se basent sur des approximations pour trouver le résultat.

Elles ne donnent pas toujours des résultats exacts.

Après recherche sur google, j'ai pleins de résultats parlant de l'intégration et de la dérivation numérique, et dans tous les pdf, ils parlent d'extrapolations ou interpolations...

[invite9ac7aecb]

Sans utiliser d'approximations ?

Les logiciels que j'ai cités sont des logiciels de calcul formel, donc oui, ils peuvent très bien te dire que l'intégrale de exp(-(x^2)/2) entre -infini et +infini vaut

 Cliquez pour afficher

racine carrée de 2 pi (si je ne me trompe pas!)

.
Et sans le faire "par coeur" (même si tout ne doit pas être calculable).

[A voir en vidéo sur Futura]

[invite6754323456711]

D'où ma première question : pourquoi nos PC numériques ne peuvent-ils pas faire de calcul infinitésimal-analytique ?

Cela concerne, me semble t-il, la différence entre la théorie des calculs à temps continu qui c'est focalisé au début sur des machines analogiques. Les fonctions de transition sont solution d'équation différentielle.

et les machines de turing qui sont des systèmes de calcul à temps discret voir thèse de Church.

Patrick

[jiherve]

Bonsoir,
en tout point équivalent à un calculateur analogique au moins pour l'intégration: DDA.
Je laisse le plaisir de chercher.
nota: Les AOP utilisés par ces machines étaient généralement à tubes ou transistors discrets, déjà dépassés fin 60's!
JR

[invite6754323456711]

Bonsoir,

Théorie des calculs pour les systèmes à temps continu

Patrick

[invite6754323456711]

Et dans le cas des ordinateurs quantiques ?

Comment peut-on prouver que nos PC quantiques et/ou analogiques sont ou ne sont pas équivalents aux machines de Turing ?[/B]

http://fr.wikipedia.org/wiki/Hypercalcul

http://www.mathrix.org/zenil/memoire.pdf

Patrick

[Amanuensis]

(...)

Il me semble percevoir une confusion entre "machine de Turing" et "puissance de la machine de Turing".

Une "machine de Turing", c'est un objet mathématique, un modèle particulier d'automate à états finis.

Les PC numériques ne sont pas des machines de Turing, ce sont des machines à signaux analogiques conçues pour que les modéliser comme une machine de Turing soit parfaitement adapté.

Les calculateurs analogiques ne peuvent pas être modélisés en toute généralité comme des machines de Turing, ça colle pas. Ce ne sont pas des automates à états finis, pour commencer !

Comme les machines concrètes que nous utilisons sont à la base des machines n'utilisant que des signaux analogiques, la classe des "calculateurs analogiques" contient les PC numériques actuels. Tout cela est cohérent, parce que les PC numériques ne sont pas des automates à états finis, mais des machines modélisables, pour toute applications pratiques, comme des automates à états finis (parce qu'ils sont conçu pour cela !).


La puissance de la machine de Turing c'est autre chose. On montre en mathématiques que d'autres automates à états finis peuvent être utilisés pour faire les mêmes calculs qu'un automate type "machine de Turing". On va alors dire qu'ils ont la puissance de la machine de Turing.

Généraliser la notion de "puissance de la machine de Turing" à autre chose que des automates à états finis n'est pas facile.

Si on accepte que les PC numériques ont la puissance de la machine de Turing, c'est à dire si on accepte que le taux (ridicule) d'erreurs résiduel dû à la réalité analogique de ces machines n'empêche pas le label "avoir la puissance de la machine de Turing", alors l'ensemble des calculateurs analogiques contient un sous-ensemble ayant la puissance de la machine de Turing.

---

La comparaison des algos "analogiques" (pour de la dérivation ou de l'intégration) et les algos numériques pour des questions similaires, la clé est le fait qu'aucune machine, analogique ou numérique, ne le fait parfaitement. La nature de l'approximation est différente, ce qui empêche de considérer les algos comme résolvant la même question dans l'absolu.

Par contre, si on pose la question de manière pratique, en donnant une borne statistique sur l'approximation du résultat, alors il est toujours possible de faire mieux avec un automate à états finis qu'avec un calculateur analogique donné.

Ainsi, en se mettant sur le terrain pratique plutôt que sur celui de l'idéalisation mathématique, les algos numériques (= conçus pour tourner sur une machine de Turing) sont au moins aussi puissants que tout calculateur analogique concret donné.

[invite6cf0b74e]

Bonjour,
j'ai lu votre réponse et la phrase ci-dessous m'intéresse beaucoup :
"Par contre, si on pose la question de manière pratique, en donnant une borne statistique sur l'approximation du résultat, alors il est toujours possible de faire mieux avec un automate à états finis qu'avec un calculateur analogique donné."

En effet, si je vous ai bien compris (pardon si ce n'est pas le cas, mais compétences en informatiques sont limitées mais le sujet m'intéresse...), tout calculs ou opérations effectué par un procédé analogique peut être simulé par un automate à états finis ? si oui, auriez vous des références permettant de dire si un automate cellulaire comme le jeu de la vie est capable des même performances, je crois avoir compris en lisant un livre de JP Delahaye que cet automate possède la propriété de "calcul universel", est ce que cela suffit pour reproduire tout procédé de calcul analogique ?
Cordialement
Paul crion.

[Amanuensis]

tout calculs ou opérations effectué par un procédé analogique peut être simulé par un automate à états finis ?

Je dirais plutôt "approché" que simulé. Un calcul analogique est limité en précision par différentes sources d'erreurs, comme le bruit thermique. Un algorithme numérique pour le même calcul pourra avoir une précision meilleure, mais les erreurs seront d'une autre nature (arrondis), avec des caractéristiques différentes.

si oui, auriez vous des références permettant de dire si un automate cellulaire comme le jeu de la vie est capable des même performances, je crois avoir compris en lisant un livre de JP Delahaye que cet automate possède la propriété de "calcul universel", est ce que cela suffit pour reproduire tout procédé de calcul analogique ?

J'ai lu la même chose, i.e., que le jeu de la vie avait la puissance de la machine de Turing, ou encore qu'on pouvait construire une machine de Turing à partir d'un automate cellulaire régi par les règles proposées par Conway, mais je n'ai pas de référence sous la main. Cela devrait être facile à trouver sur le Oueb ; avez-vous recherché en langue anglaise ?
Paul crion.[/QUOTE]

[invite6cf0b74e]

Bonjour,

"Je dirais plutôt "approché" que simulé. Un calcul analogique est limité en précision par différentes sources d'erreurs, comme le bruit thermique. Un algorithme numérique pour le même calcul pourra avoir une précision meilleure, mais les erreurs seront d'une autre nature (arrondis), avec des caractéristiques différentes."

Merci pour cette idée, le bruit thermique et le "bruit calculatoire" peuvent être vus comme deux aspects des causes d'altérations de la réponse,
je me demande si ces deux aspects peuvent être rapprochés ?
Le bruit thermique doit être calculé en utilisant la thermodynamique et la propagation des arrondis en utilisant des algorithmes de tests,
je me demande si la théorie de l'information ne permet pas de relier ces deux approches de la propagation de l'erreur ?
La propagation de l'erreur n'est elle pas la cause principale de la limitation des calculateurs dans le calcul "infinitésimal" ?
On peut la quantifier mais il se peut qu'elle limite fortement la capacité du calculateur... sacré travail pour les ingénieurs qui doivent déterminer les plages de tolérances des calculateurs...chapeau bas.
Merci encore pour votre réponse éclairante, je fonce sur le Web pour trouver des infos sur la capacité exacte des automates en terme de calcul et qui sait peut être que dans ce domaine l'erreur est compensée, ou atténuée... on verra.
Cordialement

[JPL]

Merci de bien vouloir utiliser la balise Quote pour les citations.