Discussion:Théorie des automates

Le contenu de la page n’est pas pris en charge dans d’autres langues.
Une page de Wikipédia, l'encyclopédie libre.
Autres discussions [liste]
  • Admissibilité
  • Neutralité
  • Droit d'auteur
  • Article de qualité
  • Bon article
  • Lumière sur
  • À faire
  • Archives
  • Commons

Paragraphe "La naissance d'une nouvelle science"[modifier le code]

Suite à la lecture de ce paragraphe, je confirme qu'il devrait être supprimé, pour les raisons suivantes :

L'objet du paragraphe est peu clair : de quelle "nouvelle science" parle-t-on ? On finit par comprendre que l'objet du paragraphe est - grosso-modo - de justifier, par la théorie des automates, la nature mathématique de la réalité. Nipou me dit sur sa PdD que cela correspond à la thèse de Church–Turing–Deutsch, mais un des problèmes est que ce paragraphe ne parle absolument pas de la thèse de Church–Turing–Deutsch, mais parle de la thèse de Church–Turing, qui est hors-sujet car la thèse de Church-Turing ne peut suffire à justifier de la réalité, de part la nature discrète des MT alors que la réalité est continue (analyse et conclusion de Deutsch lui-même).

Donc le paragraphe qui commence à "La thèse de Church-Turing qui postule..." et qui se finit à "Par conséquent, tout phénomène naturel est calculable..." est inexact , pour ne pas dire faux, de ce fait.

Mais, si on remplace la thèse de Church-Turing par la thèse de Church–Turing–Deutsch, et les MT par des MT quantiques, le paragraphe a-t-il plus de sens ? Oui, mais je ne vois plus alors ce qu'il viendrait faire dans cet article, qui concerne - ne l'oublions pas - la théorie des automates, fondée sur les MT classiques. Certes, les MTQ possèdent de nombreux aspects en communs avec les MT, mais aucun de ces aspects en commun ne justifie la nature mathématique de la réalité : ce sont justement les aspects des MTQ propres à celles-ci, et en dehors de la théorie des automates qui pourraient le justifier (aspects non déterministes et continuité). Tout le raisonnement de ce paragraphe ne me semble pas sourçable, et est probablement un TI. Chaque phrase peut être isolément sourçable (mais j'ai des doutes pour la seconde), mais le raisonnement qui les unit, qui est matérialisé par le "par conséquent", me semble inédit et discutable.

De plus, le paragraphe est excessivement non-neutre car globalement affirmatif, alors que tout cela est fondé au mieux sur une thèse et donc rien n'est démontré. Par exemple, les phrases "L'étude des automates est donc, en fait, l'étude de la structure fine de l'univers et est, en ce sens, une science naturelle", ou bien "est une réponse finale à la question de la nature de la mathématique", sont affirmatives et présentent les choses comme une vérité absolue et établie, ce qui est très loin d'être le cas et non-neutre.

Donc, ce paragraphe est au mieux hors-sujet (d'un article centré sur la théorie des automates), et - profondément rémanié et neutralisé - pourrait à la limite appartenir à un article sur la thèse de Church–Turing–Deutsch, et encore. Je demande à Nipou d'accepter la suppression de ce paragraphe, et de fonder la structure des raisonnement exposés et l'approche du sujet (le sujet est la théorie des automates) sur des sources de qualité. --Jean-Christophe BENOIST (d) 9 novembre 2011 à 21:37 (CET)[répondre]

Un petit complément : je pense refaire (à terme, pour le moment j'ai d'autres chantiers) cet article selon l'approche et le plan de l'ouvrage de référence "Introduction to Automata Theory, Languages and Computation". L'approche et le plan de cet ouvrage ne fait nulle place aux considérations sur la mathématisation de l'univers. C'est un choix, et on pourrait opposer à cette approche (toutefois très classique et très répandue), un autre ouvrage de référence sur la théorie des automates qui ferait une place à ces considérations. Mais cette source reste à trouver. En tout les cas, en cas de désaccord éditorial (c'est ici le cas), il faut se fonder sur des ouvrages de référence consacrés au sujet, et s'inspirer de leur approche (cela semble évident, mais il faut le rappeler). Mais il faut éviter ce citer et compiler arbitrairement des bribes d'informations en provenance d'ouvrages consacrés à d'autres sujets (de philosophie, sur le déterminisme en général etc..) qui font allusion à la théorie des automates. Ce serait acceptable en l'absence de polémique et de désaccord éditorial, mais pas en présence de polémiques et de désaccord. --Jean-Christophe BENOIST (d) 9 novembre 2011 à 22:26 (CET)[répondre]

Je suis tout à fait d'accord, il s'agit d'une prise de position parfaitement idéologique :-) mais rien n'empêche d'aborder cette question de front de façon objective. Effectivement, la littérature «philosophique» est limitée et il faut être un Geek fini pour s'intéresser à cette matière absconse ;-)

Dans l’introduction de la la thèse de Church il y a ces paragraphes avec une référence en français :

Dans une forme dite "physique"[1], elle affirme que la notion physique de la calculabilité, définie comme étant tout traitement systématique réalisable par un processus physique ou mécanique, peut être exprimée par un ensemble de règles de calcul, défini de plusieurs façons dont on a pu démontrer mathématiquement qu'elles sont équivalentes.

Dans sa forme dite "psychologique"[1] elle affirme que la notion intuitive de calculabilité, qui est liée à ce qu'un être humain considère comme effectivement calculable ou non, peut également être exprimée par ces mêmes ensembles de règles de calcul formelles.


Je ferais remarquer que les automates quantiques sont également strictement inclus dans la classe des langages récursifs (jusqu'à véritable preuve du contraire) et s'ils ne le sont pas, ils ne possèdent probablement qu'un petit ensemble fini de fonctions non Turing calculables. Il faudrait expliquer clairement la différence entre la calculabilité absolue et la calculabilité relative (complexité du calcul).


De même, il faudrait distinguer la conception constructiviste de l'approche par oracle non-déterministe et des hiérarchies de langages non-calculables. Séparer le réel de la réflexion sur le réel.


--Nipou (d) 10 novembre 2011 à 02:52 (CET)[répondre]

Le fait que ce soit une position idéologique n'est pas un problème, si les assertions sont attribuées et sourcées. Ici, il n'y a ni l'un ni l'autre.
La forme physique de la thèse de Church n'est soutenable avec des MT classiques (et avec la théorie des automates) que si les hypothèses de Gandy sont vraies (voir [1] par exemple). Or, Deutsch lui-même (pour ne citer que lui) n'est pas d'accord avec les hypothèses de Gandy, et bien d'autres chercheurs. Il faut expliquer tout cela au lieu de faire des affirmations fracassantes.. Il y a sans doute un lieu dans WP pour exposer tout ceci en détail, mais ce n'est pas cet article ! Il existe d'ailleurs sans doute une bonne source pour la liaison entre thèse physique de Church et la "déraisonnable efficacité des maths", c'est Dowek. Mais il faut se fonder sur ce genre de sources, attribuer à Dowek etc.. Et pas dans cet article ! --Jean-Christophe BENOIST (d) 10 novembre 2011 à 17:40 (CET)[répondre]

"(1a) a lower bound on the linear dimensions of any of the parts, (1b) an upper bound on speed of propagation (the velocity of light), (2) discrete progress of the machine, and (3) deterministic behavior—he produces a theorem that "What can be calculated by a device satisfying principles I–IV is computable."

En fait, le principal problème vient de l'hypothèse du continu (qui est inutile) et du fait que même si le continu existait réellement, l'hypothèse de "discrete progress" est trop forte, nous n'avons réellement besoins que d'un "progrès discrétisable".

Il en est de même pour le déterminisme qui nécessiterait la non action à distance. Cette hypothèse est complètement inutile, seul le lien causal est nécessaire ; celui-ci pourrait exister sans l'espace et même se trouver en désordre dans le temps.

Mais faute de ces critiques non-publiés, je suis prêt à accepter Gandy tel quel.--Nipou (d) 11 novembre 2011 à 04:33 (CET)[répondre]



  1. a et b Gilles Dowek Les Métamorphoses du calcul Le Pommier. 2007

La vulgarisation est est-elle une ?[modifier le code]

Au lieu de "Vulgarisation", cela me semble plutôt un "Historique" qui contient une description téléologique de certains faits, pour aboutir encore à Chomsky. J'ai essayé de voir comment arranger cela, sans y être parvenu. Je propose la suppression de cette section, ainsi que des références correspondantes.

L'introduction, avec ses références peu convaincantes à Hopcroft & Ullman, devrait aussi être revue.--ManiacParisien (d) 7 décembre 2011 à 07:17 (CET)[répondre]