Répondre à la discussion
Page 1 sur 3 12 DernièreDernière
Affichage des résultats 1 à 30 sur 73

Programme non algorithmique : libre arbitre et hasard intrinsèque



  1. #1
    spi100

    Programme non algorithmique : libre arbitre et hasard intrinsèque


    ------

    Le titre est volontairement provocateur. Comment est - il possible de juxtaposer le mot "programme" synonyme d'algorithme avec le terme non - alogorithmique !

    En fait l'on entend par programme non algorithmique, un programme qui réalise des choses qui ne sont pas explicités dans le programme. En d'autres termes, un programme dont le comportement échappe au programmeur.
    Les exemples les plus connus de ce type de programmes, sont les automates cellulaires. Un automate cellulaire est un ensemble de cellules qui peuvent prendre différents états, l'état de chaque cellule étant définit par celui de ces voisines.
    La règle qui régit un automate est souvent très simple, il peut par exemple s'agir du jeu de la majorité : une cellule peut être blanche ou noire, si la majorité des premières voisines est blanche alors la cellule devient blanche, sinon noire. Dans le cas où il y a autant de blanches que de noires, on tire au sort. Pour les physiciens, cet automate est strictement équivalent à modèle d'Ising à température nulle.
    Ce qui est fascinant avec les automates cellulaires, c'est que même si la règle est très simple, il n'est pas possible de prévoir le comportement simplement en regardant le programme.
    Pour prévoir le comportement il faut soit executer le programme, soit faire un modèle mathématique.

    Si je crée ce fil c'est un peu en réponse au fil 'l'algorithme ultime' ou l'idée que l'histoire de l'univers est contenu dans un code, et serait donc prévisible si l'on connaissait ce code. En fait ces points de vues sont AMHA faux. Et je pense qu'une bonne base de discussion sur ce thème est ce texte tiré de 'A new kind of science' de Wolfram, trouvé sur le web

    http://www.admiroutes.asso.fr/larevu...6/francois.htm

    Depuis l'Antiquité, il a toujours régné un grand mystère autour de cette question du contraste entre l'univers pouvant suivre des lois définies, et nous en tant qu'humains pouvant souvent prendre des décisions au sujet de nos actes d'une manière qui semble affranchie de toute loi évidente.
    Mais à partir des découvertes de ce livre, il semble finalement possible d'en donner une explication. Et je crois que la clé se trouve dans le phénomène d'irréductibilité computationnelle qui implique que même si un système peut suivre des lois sous-jacentes définies, son comportement général peut néanmoins présenter des formes qui ne peuvent fondamentalement pas être décrites par des lois raisonnées.
    Si l'évolution d'un système correspond à une computation irréductible, alors la seule façon de trouver comment le système va se comporter est de réaliser cette computation - avec pour conséquence qu'il ne peut fondamentalement pas y avoir de loi permettant d'accéder à ce comportement de façon plus directe.
    Et c'est cela, je crois, qui est à l'origine de l'apparente liberté de la volonté humaine. Car même si tous les composants de notre cerveau suivent vraisemblablement des lois définies, je soupçonne fortement que leur comportement général corresponde à une irréductible computation dont le résultat ne peut jamais être trouvé par des lois raisonnées.
    On peut déjà voir quelque chose de très ressemblant se produire dans un simple système comme l'automate cellulaire de la figure présentée à gauche. Car même si les lois de ce système sont parfaitement définies, son comportement général finit par être suffisamment complexe pour que beaucoup de ses caractéristiques semblent n'obéir à aucune loi évidente.
    Si on devait débattre de l'apparence du comportement de cet automate cellulaire, on pourrait tout à fait dire qu'il semble faire un peu ce qu'il veut - et lui attribuer une sorte de libre volonté.
    Ce comportement a-t-il une chance d'être raisonné ? Car si on étudie les cellules individuelles à l'intérieur de l'automate, on peut pleinement s'apercevoir qu'elles ne font que suivre des règles strictes, et sont privées de toute espèce de liberté.
    Et à un certain niveau, on pourrait dire la même chose des cellules nerveuses individuelles de notre cerveau. Pourtant celui-ci dans son entier arrive à se comporter avec une certaine liberté apparente.
    La science traditionnelle a rendu cela très difficile à comprendre. Car on prétend normalement que si on se contente de trouver des règles sous-jacentes gouvernant les composants d'un système, alors ces règles devraient suffire à nous dire tout ce qui est important de savoir sur le système.
    Mais comme nous l'avons constamment constaté dans ce livre, cette vision des choses n'est même pas approximativement correcte. Il peut en fait y avoir largement plus de choses dans le comportement d'un système que dans tout ce qu'on pourrait essayer d'y entrevoir en se limitant à ses règles sous-jacentes. C'est une conséquence fondamentale du phénomène d'irréductibilité computationnelle.
    Car si un système est computationnellement irréductible, cela signifie qu'il existe une séparation tangible entre les règles sous-jacentes du système et son comportement général, associée à la quantité de travail computationnel nécessaire pour passer de l'un à l'autre.
    Je crois que c'est dans cette séparation, que repose la prime origine de l'apparente liberté dont semblent jouir toutes sortes de systèmes - qu'il s'agisse de systèmes abstraits comme les automates cellulaires ou de systèmes concrets comme le cerveau.
    Mais finalement, qu'est-ce qui nous fait dire qu'il y a de la liberté dans ce qu'un système fait ? En pratique, le principal critère semble être l'impossibilité de prédire son comportement. Si nous pouvions le prévoir, il nous montrerait qu'il est déterminé d'une façon définie, et donc ne pourrait être qualifié de libre. Mais avec nos méthodes de perception et d'analyse, nous avons besoin d'un comportement plutôt simple pour nous permettre d'identifier des règles générales nous laissant faire des prédictions raisonnables les concernant. Et ce genre de comportement est assez courant, même chez les organismes vivants. En particulier chez les animaux les moins évolués, il existe toutes sortes de situations où de très simples et très prévisibles réponses à des stimuli sont observées. Mais ces réponses sont normalement considérées comme des réflexes inévitables ne laissant aucune place aux décisions ou à la liberté.
    Et dès que le comportement devient plus complexe, nous avons vite tendance à imaginer qu'il est associé à une certaine forme de liberté sous-jacente. Nous introduisons cette dose de liberté, car avec l'intuition traditionnelle nous avons toujours une sorte de réticence à penser qu'une réelle imprévisibilité puisse émerger dans un système qui ne fait que suivre des règles sous-jacentes définies.
    Et ainsi, pour expliquer notre comportement humain, on prétend souvent qu'il doit se passer quelque chose de plus fondamental - et peut-être quelque chose de propre aux humains.
    Dans le passé, la croyance la plus courante était basée sur l'existence d'une certaine forme d'influence extérieure du destin - associée peut-être à l'intervention d'un être surnaturel ou à la configuration des corps célestes. Dans des temps plus récents, la sensibilité aux conditions initiales et l'incertitude quantique ont été proposées comme des explications plus scientifiques.
    Mais un peu comme dans la discussion sur le hasard (voir chapitre 6), nous n'avons pas réellement besoin de ce genre d'explications. Car comme nous l'avons vu si souvent dans ce livre, même les systèmes dotés de règles sous-jacentes assez simples et définies peuvent produire des comportements si complexes qu'ils vont paraître libres de toutes règles apparentes.
    Le point crucial est que ces comportements apparaissent simplement pendant l'évolution intrinsèque du système - sans avoir besoin d'aucune entrée supplémentaire de l'extérieur ou d'aucune sorte de source explicite d'aléatoire.
    Et je crois que c'est ce type de processus intrinsèque - dont nous savons maintenant qu'il apparaît dans un large éventail de systèmes - qui est le responsable primaire de l'apparente liberté dans les opérations de notre cerveau.
    Mais cela ne veut pas dire que tout ce qui advient dans notre cerveau a une origine intrinsèque. En effet, ce qui semble se passer en pratique est le fait que nous recevons des entrées extérieures conduisant à une chaîne de pensées suivant son cours pendant un certain temps, puis celle-ci s'éteint jusqu'à l'entrée suivante. Et souvent cette chaîne de pensées est influencée par la mémoire développée par des entrées passées - faisant varier cette chaîne de pensées même si l'entrée est exactement la même.
    Mais il semble vraisemblable que les étapes individuelles de chaque chaîne de pensées suivent des règles sous-jacentes assez définies. Et le point crucial est que je suspecte que la computation réalisée en appliquant ces règles va souvent être assez sophistiquée pour être computationnellement irréductible - et par conséquent cette chaîne va produire intrinsèquement un comportement nous paraissant libre de toute loi évidente.

    -----

  2. Publicité
  3. #2
    deep_turtle

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Ce qui est fascinant avec les automates cellulaires, c'est que même si la règle est très simple, il n'est pas possible de prévoir le comportement simplement en regardant le programme.
    Pour prévoir le comportement il faut soit executer le programme, soit faire un modèle mathématique.
    J'ai toujours un peu de mal avec ce genre de sujet. Je ne vois pas en quoi c'est fascinant ou particulier. N'est-ce pas le lot de toutes les lois en physique ? On ne peut pas non plus "prévoir" le comportement d'une onde électromagnétique juste en "regardant" les équations de Maxwell, il faut les résoudre avec certaines conditions initiales. Quelle est la différence fondamentale qui m'échappe ?

  4. #3
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par deep_turtle
    J'ai toujours un peu de mal avec ce genre de sujet. Je ne vois pas en quoi c'est fascinant ou particulier. N'est-ce pas le lot de toutes les lois en physique ? On ne peut pas non plus "prévoir" le comportement d'une onde électromagnétique juste en "regardant" les équations de Maxwell, il faut les résoudre avec certaines conditions initiales. Quelle est la différence fondamentale qui m'échappe ?
    Il faut bien comprendre que je me place du point de vue de l'écriture d'un algorithme dont on ne peut pas deviner le comportement à moins ... d'en faire un modèle mathématique.

    Dans l'exemple de lois de Maxwell, tu me donnes déjà la formulation mathématique, tu te places hors de la notion d'algorithme, ou si tu préfères, tu as court-cicuité cette notion en passant à l'étape au-dessus. Tu ne cherches pas l'automate sous-jacent à la formulation de l'électro-magnétisme.

    Il faut bien voir que les automates cellulaires intéressants, sont modélisables par des équations non-linéaire. Equations que l'on ne sait pas résoudre en générale, qui se prêtent très mal aux traitements perturbatifs classiques, et présentent souvent un caractère chaotique. Donc même en ayant fait la modélisation mathématique, l'hyper sensibilité aux conditions initiales de ces équations, fait que ta modélisation ne te permet pas de prévoir à long terme le comportement de ton système.

    Mais attention, je ne prétends pas que les automates cellulaires se substituent aux équations de la physique, il s'agit plutot d'un traitement alternatif, plus facile à mettre en oeuvre sur un ordinateur, et aussi plus facile à appréhender car tu réfléchis en termes de cellules et d'état en fonction du voisinage de la cellule.

    J'essaie d'illustrer. Si tu veux modéliser la propagation d'un feu de forêt, tu peux construire les équations de cette propagation, puis la discrétiser pour résolution numérique. Dans ce cas, ta modélisation sur grille est ton automate.
    Mais tu peux aussi faire l'inverse, et construire directement l'automate d'après la compréhension que tu as du phénomène. Dans le cas de la propagation, la notion de cellule allumée ou éteinte en fonction de l'état des cellules voisines est très intuitive. Et tu travailles alors directement sur l'automate que tu as construit. D'un point de vue purement pratique, quitte à se ramener à une simulation numérique, autant se passer des équations.
    Dernière modification par spi100 ; 30/08/2004 à 11h07.

  5. #4
    Lambda0

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Sur l'équivalence entre la machine de Turing (et donc la notion d'algorithme telle que le conçoit traditionnellement) et les automates cellulaires.
    A méditer

    http://nazim.fates.free.fr/Epistemo/.../partie2B.html

  6. A voir en vidéo sur Futura
  7. #5
    pi-r2

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Que veux tu dire par 'à méditer ?'. Quelles sont les conclusions que tu en tires ?
    Les bonnes idées triomphent toujours... C'est à cela qu'on reconnait qu'elles étaient bonnes !

  8. #6
    Lambda0

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Rep Pi-r2

    En terme de calculabilité, les automates cellulaires ne semblent pas apporter plus que la machine de Turing.

    D'une façon générale, dans cette discussion, comme dans celle à laquelle elle fait suite, les physiciens ont exprimé leur point de vue, mais il manque en fait un intervenant très important : un mathématicien maitrisant la théorie de la calculabilité et capable de dire effectivement ce qu'est un programme et quelles en sont les limitations. Faute de quoi, la discussion finit par tourner en rond.
    Je ne suis pas ce mathématicien, mais je connais l'existence de cette théorie et je vois bien qu'il manque quelque chose de très important dans ces raisonnements purement physiques.

    Avant d'invoquer des arguments physiques, comme le principe d'incertitude, on peut d'abord se demander quelles sont les limites fondamentales de la notion de "programme", ce qu'a fait Alan Turing il y a plus de cinquante ans.
    Je reformulerais donc la question de la façon suivante :
    "L'univers peut-il être décrit par une fonction calculable, au sens de la théorie de la calculabilité de Turing ?"

    Si la réponse à cette question est positive, on peut ensuite s'intéresser aux arguments physiques. En faisant l'inverse, on parle d'"algorithmes" et de programmes sans avoir vraiment compris de quoi il s'agit.

  9. Publicité
  10. #7
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par Lambda0
    Rep Pi-r2

    En terme de calculabilité, les automates cellulaires ne semblent pas apporter plus que la machine de Turing.

    D'une façon générale, dans cette discussion, comme dans celle à laquelle elle fait suite, les physiciens ont exprimé leur point de vue, mais il manque en fait un intervenant très important : un mathématicien maitrisant la théorie de la calculabilité et capable de dire effectivement ce qu'est un programme et quelles en sont les limitations. Faute de quoi, la discussion finit par tourner en rond.
    Je ne suis pas ce mathématicien, mais je connais l'existence de cette théorie et je vois bien qu'il manque quelque chose de très important dans ces raisonnements purement physiques.

    Avant d'invoquer des arguments physiques, comme le principe d'incertitude, on peut d'abord se demander quelles sont les limites fondamentales de la notion de "programme", ce qu'a fait Alan Turing il y a plus de cinquante ans.
    Je reformulerais donc la question de la façon suivante :
    "L'univers peut-il être décrit par une fonction calculable, au sens de la théorie de la calculabilité de Turing ?"

    Si la réponse à cette question est positive, on peut ensuite s'intéresser aux arguments physiques. En faisant l'inverse, on parle d'"algorithmes" et de programmes sans avoir vraiment compris de quoi il s'agit.
    On peut déjà commencer par donner la définition d'un algorithme, j'ai la définition suivante dans la Wikipedia :

    Un algorithme est une méthode de résolution de problème énoncée sous la forme d'une série d'opérations à effectuer.
    Il faut bien comprendre ce qu'est classiquement un programme : c'est une succession de N actions, et la dernière action fournit la solution au problème posé. Le comportement du programme est complètement contenu dans l'algorithme écrit, et chaque étape est parfaitement pensée et contrôlée par le développeur. Une personne qui n'a pas écrit le programme, lisant l'algorithme avec suffisamment de mémoire et de concentration, pourra indiquer ce qu'il fait.

    Dans un automate (réseau de neurones, système multi-agents), c'est le résultat de la collaboration entre entités qui aboutit à la solution du problème. L'algorithme utilisé code explicitement le comportement des agents, mais la conséquence du comportement n'est pas explicitement contenu dans le code. C'est ce point qui est important, et ce n'est pas tellement un problème de calculabilité.

    Les informaticiens découvrent ce type de systèmes pour la résolution de problèmes non triviaux, mais les physiciens y sont naturellement confrontés depuis le début de la physique avec le problème à N corps. Il est aussi parfaitement impossible de prévoir le comportement d'un système d'Ising à plus de 2D, etc.

    Ce qui est vraiment troublant, c'est que l'on soit incapable de modéliser correctement les systèmes collaboratifs simples. Par exemple, qui est actuellement capable de donner un moyen effectif d'énumérer les structures stables d'un automate aussi simple que le jeu de la vie ? En fait, personne !

    Pour en revenir au problème de la calculabilité, sans être mathématicien, je suis quand même certain que les automates ne sont pas plus puissants. Mais je vois plutot ça en analogie avec un programme récursif : ecrire un algorithme d'exploration d'arbre en récursif prend 10 lignes mais tu peux aussi le faire sans la récursivité, mais alors ton programe fera 100, 1000 lignes, et tu devras tenir compte de toutes une série de cas particuliers. Un automate, ou plus généralement un système collaboratif, peut être un moyen d'écrire un programme plus synthétique permettant de résoudre un problème complexe, qui prendrait un nombre énorme de lignes de code et de spécifications s'il fallait le coder sous forme d'un algorithme séquentiel classique (pense par exemple aux réseaux neuronaux).

  11. #8
    Lambda0

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Bonjour Spi100

    Quelques commentaires et réponse

    "On peut déjà commencer par donner la définition d'un algorithme,
    j'ai la définition suivante dans la Wikipedia :
    Citation:
    Un algorithme est une méthode de résolution de problème énoncée sous la forme d'une série d'opérations à effectuer."

    Il ne s'agit bien que d'un début de définition. Voir la réponse développée.


    "Il faut bien comprendre ce qu'est classiquement un programme : c'est une succession de N actions, et la dernière action fournit la solution au problème posé. Le comportement du programme est complètement contenu dans l'algorithme écrit, et chaque étape est parfaitement pensée et contrôlée par le développeur. Une personne qui n'a pas écrit le programme, lisant l'algorithme avec suffisamment de mémoire et de concentration, pourra indiquer ce qu'il fait."

    Pas d'accord sur tout.
    Un programme ne se termine pas nécessairement (exemple: gestion d'un central téléphonique) et pour ce qui est de comprendre ce que fait un programme en l'examinant, on retombe sur un problème de calculabilité analoge à celui de la machine de Turing essayant de déterminer si une autre machine de Turing s'arrête (voir réponse développée).
    J'arrête tout de suite ton objection : non je ne considère pas a priori que le cerveau humain est équivalent à une machine de Turing.
    Je met simplement en doute le fait qu'il soit possible de "comprendre" le fonctionnement de tout programme en un temps fini.


    "Dans un automate (réseau de neurones, système multi-agents), c'est le résultat de la collaboration entre entités qui aboutit à la solution du problème. L'algorithme utilisé code explicitement le comportement des agents, mais la conséquence du comportement n'est pas explicitement contenu dans le code. C'est ce point qui est important, et ce n'est pas tellement un problème de calculabilité."

    Bien au contraire : le fond du problème est bien une question de calculabilité. Le débat portait sur l'existence (et j'ai rajouté "sur la calculabilité") d'une fonction décrivant l'univers. A la calculabilité au sens de la machine de Turing, tu opposais une calculabilité au sens des automates cellulaires, et je donnais un lien suggérant une équivalence entre les deux, malgré les différences entre les deux. Le point est que l'automate cellulaire, tout comme la machine de Turing, sont déterministes, et leurs différences sont peut-être finalement assez superficielles.

    "Les informaticiens découvrent ce type de systèmes pour la résolution de problèmes non triviaux, mais les physiciens y sont naturellement confrontés depuis le début de la physique avec le problème à N corps. Il est aussi parfaitement impossible de prévoir le comportement d'un système d'Ising à plus de 2D, etc."

    Ce n'est pas un problème d'informatique. En remontant le fil, on bute sur des problèmes mathématiques assez fondamentaux qui ont surgit
    dans la première moitié du 20ème siècle. Celà dépasse largement les
    quelques problèmes de précision numériques qu'ont peut rencontrer
    quand on discrétise des équations pour les résoudre numériquement.
    Ces problèmes mettent en question la capacité même des mathématiques à résoudre certains problèmes (voir ce qu'en dit Godel).
    Or, la physique est écrite en langage mathématique...


    "Ce qui est vraiment troublant, c'est que l'on soit incapable de modéliser correctement les systèmes collaboratifs simples. Par exemple, qui est actuellement capable de donner un moyen effectif d'énumérer les structures stables d'un automate aussi simple que le jeu de la vie ?
    En fait, personne !"

    Très juste. Alors que les règles d'un automates cellulaire comme le "jeu de la vie" sont très simples.



    Réponse développée

    Bien sûr, on trouvera une définition du terme "programme" dans n'importe quelle encyclopédie. Tout comme on y trouvera la mécanique quantique et la relativité générale résumées en dix lignes.
    En physique, n'importe qui peut disserter sur la mécanique quantique et exprimer des idées générales que l'on trouve un peu partout, mais en tant que physicien, je pense que tu distingue assez vite ceux qui ont effectivement ferraillé avec les équations (et les ont comprises!) de ceux qui ont simplement lu un ouvrage de vulgarisation grand public ou le peut-être le 1er chapitre du Cohen-Tanoudji.

    Je soupçonne simplement qu'il en va de même avec la notion de programme. La plupart des intervenants ont probablement écrit quelques lignes de codes dans un langage quelconque, mais ce n'est pas une bonne base de discussion.
    C'est comme si on essayait de discuter de concepts pointus en mécanique quantique (par exemple) en se basant sur des réalisations
    technologiques particulières.

    En l'occurence, dans ce débat, la bonne base à considérer est la théorie de la calculabilité, et les travaux de Alan Turing et Von Neuman. Le bon modèle théorique à considérer est celui de la machine de Turing.
    Or cette théorie de Turing exhibe certaines fonctions qui ont pour particularité de ne pas être calculables.
    Un exemple célèbre de fonction non calculable est la fonction qui à une machine de Turing associe le nombre d'opérations exécutée par la machine avant son arrêt. Une conséquence pratique est qu'il est impossible d'écrire un programme capable de prédire le résultat de tout autre programme, ni même de dire si tout autre propramme se termine en un temps fini et fournit un résultat.
    Ce n'est qu'un exemple.

    D'où ma question :
    Indépendamment de toute considération physique (liée par exemple au principe d'incertitude ou à l'impossibilité de connaitre l'état de l'univers à un instant donné), n'existe-t-il pas quelque part une contradiction logique qui ferait que la fonction décrivant l'univers (sous réserve de son existence) n'est pas calculable ?

    Remarque qu'il n'est pas nécessaire de démontrer l'existence de cette fonction pour démontrer son éventuelle non-calculabilité.
    C'est ce qui me fait dire que la démonstration de non-calculabilité peut éventuellement être menée avant toute considération physique.

    Mais, je le répète, je n'ai qu'une connaissance superficielle de la théorie de la calculabilité. C'est pourquoi je pense que l'intervention d'un mathématicien ayant un peu réfléchi aux implications ferait bien avancer la discussion.

    En attendant, voici quelques références : définition et thèmes de recherche sur la calculabilité.
    Noter, en lisant la dernière référence, que tout celà n'est pas totalement déconnecté de la physique : voir la notion de machine
    de Turing quantique.


    http://fr.wikipedia.org/wiki/Machine_de_Turing
    http://www.iut-nantes.univ-nantes.fr...alculable.html

    http://www.asmp.fr/travaux/gpw/philo...rt3/7zwirn.pdf

    Calcul quantique
    http://www-leibniz.imag.fr/perso/r7/...rs/rapport.pdf

  12. #9
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par Lambda0
    dans la première moitié du 20ème siècle. Celà dépasse largement les
    quelques problèmes de précision numériques qu'ont peut rencontrer
    quand on discrétise des équations pour les résoudre numériquement.
    Pour le problème à N corps, ce n'est pas une question de précision numérique qui pose problème. C'est beaucoup plus profond que ça. Il s'agit de l'incapacité de résoudre analytiquement le problème et de son caractère intrinsèquement chaotique.


    Je ne vois pas pourquoi tu veux absolument opposer machine de turing, et automate cellulaires. Ce n'est pas mon propos et personne dans ce fil n'a argumenté dans ce sens.
    Les automates cellulaires et réseaux neuronaux sont justes une classe d'algorithmes, nous sommes parfaitement d'accord.

    J'ai dû traiter des problèmes d'OCR et de reconnaissance de formes avec ce type de programmes, et je sais qui si j'avais du spécifier moi - même tout ce que le programme a appris et deviné, je ne serais jamais arrivé au bout du problème.

    Mais effectivement je ne suis pas mathématicien, et peut être pourrais tu expliquer un peu plus ce qu'est la calculabilité ?
    Dernière modification par spi100 ; 01/09/2004 à 16h01.

  13. #10
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par Lambda0
    Pas d'accord sur tout.
    Un programme ne se termine pas nécessairement (exemple: gestion d'un central téléphonique)
    Je ne comprends pas ton exemple. Evidemment que tant qu'il y a des appels il faut les traiter. Mais le traitement d'un appel va bien se faire selon une procédure explicite, en un nombre fini d'étapes ? De surcroit j'espère aussi que dans l'organisation d'un central, on s'arrange pour qu'il n'y ait pas d'interactions entre les appels.
    Dernière modification par spi100 ; 01/09/2004 à 16h44.

  14. #11
    mtheory

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Bonsoir.J'ai une question pour lambda0:
    Serais-tu un adepte du Grand Roger P?

  15. #12
    pi-r2

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    D'abord pour bien clarifier les choses, il n'y a pas de différence de possibilités entre une machine de turing, un réseau neuronal à nombre fini de neurones ou un automate cellulaire fini. Ils sont équivalents du point de vue de la calculabilité.
    Pour la calculabilité de l'univers j'ose une petite démonstration: Le programme capable de calculer l'univers est par restriction capable de calculer le résultat de tout algorithme tournant sur une machine de Turing. Ce 'programme' serait donc d'une 'classe' supérieure et au moins équivalent à un réseau infini (pas aussi grand qu'on le veut, infini). Donc l'univers n'est pas calculable. Il ne peut pas non plus être restreint à une série de lois physiques calculables: il restera toujours de l'imprévu, imprévisible.
    Les bonnes idées triomphent toujours... C'est à cela qu'on reconnait qu'elles étaient bonnes !

  16. Publicité
  17. #13
    Lambda0

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Rep Spi100

    alors j'ai mal compris ton premier texte, ou je l'ai interprété à ma façon. Il me semblait que tu présentais les automates cellulaires comme fondamentalement plus "puissants" qu'un programme séquentiel traditionnel par ce qu'on n'y retrouvait pas explicitement un algorithme. Si ce n'est pas le cas, nous sommes bien d'accord.
    L'intérêt qu'il peut y avoir à raisonner sur les propriétés des machines de Turing plutôt que sur les automates cellulaires est que ce modèle est plus simple.
    Tout celà sous réserve : je répète que je ne suis pas spécialiste de ce domaine

    Sur le problème à N-corps
    Je ne vois pas en quoi le fait qu'il n'y pas de solution analytique est fondamental. Très peu de problèmes physiques ont une solution analytique exacte. Tu voulais peut-être dire que ce qui est fondamental est la nature chaotique de certains systèmes d'équations différentielles. Là, je serais d'accord.
    Mon domaine est l'électromagnétisme et le moindre calcul de diffraction conduit à des systèmes d'équations insolubles.

    Calculabilité : une fonction est calculable s'il existe une machine de Turing la calculant en un temps fini. Voir la définition d'une machine de Turing sur les références déjà données.

    Mtheory:
    Bonjour
    Connait pas ce Roger P

  18. #14
    mtheory

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Roger Penrose,l'auteur de 'l'esprit,l'ordinateur et les lois de la physique'.
    Cela traite de la machine de Turing,le lambda calcul de Church ,la théorie de la complexité,de la calculabilité,le théorème de Godël et les relations avec la MQ,la RG et finalement la GQ.
    Je serais étonné que tu ne connaisses pas.

  19. #15
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par Lambda0
    Rep Spi100

    alors j'ai mal compris ton premier texte, ou je l'ai interprété à ma façon. Il me semblait que tu présentais les automates cellulaires comme fondamentalement plus "puissants" qu'un programme séquentiel traditionnel par ce qu'on n'y retrouvait pas explicitement un algorithme. Si ce n'est pas le cas, nous sommes bien d'accord.
    Non, bien sur ce n'est pas le cas. Nous sommes bien d'accord.

    Citation Envoyé par Lambda0
    L'intérêt qu'il peut y avoir à raisonner sur les propriétés des machines de Turing plutôt que sur les automates cellulaires est que ce modèle est plus simple.
    Tout celà sous réserve : je répète que je ne suis pas spécialiste de ce domaine
    Justement non, ce n'est pas forcemment plus simple. C'est parfois plus simple de réfléchir directement sur l'automate, comme c'est plus intuitif, ça aide à construire des heuristiques (voir par exemple les algo génétiques ou l'algo des fourmis).

    Sur le problème à N-corps
    Je ne vois pas en quoi le fait qu'il n'y pas de solution analytique est fondamental. Très peu de problèmes physiques ont une solution analytique exacte. Tu voulais peut-être dire que ce qui est fondamental est la nature chaotique de certains systèmes d'équations différentielles. Là, je serais d'accord.
    Mon domaine est l'électromagnétisme et le moindre calcul de diffraction conduit à des systèmes d'équations insolubles.
    La je suis un peu comme toi, loin d'être un spécialiste, mais il me semble que dire que tu peux résoudre un problème analytiquement, veut dire être capable de fournir un moyen effectif de construire la solution sous forme de séries.

    Et je crois que dans le cas général du problème à N corps quelquesoit le traitement perturbatif et le développement en série que tu cherches à faire, tu ne peux pas éviter les termes divergents. C'est à dire qu'ils présentent effectivement du chaos conservatif.

    Calculabilité : une fonction est calculable s'il existe une machine de Turing la calculant en un temps fini. Voir la définition d'une machine de Turing sur les références déjà données.
    Est- ce que temps fini et synonyme 'de nombre d'étapes fini' ?

    Mtheory:
    Bonjour
    Connait pas ce Roger P
    Je crois que Mtheory veut parler de Roger Penrose, un dangereux spiritualiste
    Dernière modification par spi100 ; 01/09/2004 à 18h17.

  20. #16
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par pi-r2
    D'abord pour bien clarifier les choses, il n'y a pas de différence de possibilités entre une machine de turing, un réseau neuronal à nombre fini de neurones ou un automate cellulaire fini. Ils sont équivalents du point de vue de la calculabilité.
    Oui, du point de vue de la calculabilité. Mais du point de vue de la mise en oeuvre, c'est tout à fait différent. Ce qui est facile à mettre en oeuvre avec un réseau de neurones, peut être un enfer à mettre en oeuvre avec un algo explicite et inversement. Tout dépend bien sûr du problème à traiter.

  21. #17
    mtheory

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par spi100
    Je crois que Mtheory veut parler de Roger Penrose, un dangereux spiritualiste
    Exact!Et c'est vrai que lui et sa famille ne sont pas des gens très sérieux ni bien malin.
    La preuve:

    http://www-gap.dcs.st-and.ac.uk/~his...s/Penrose.html

    http://www.worldofescher.com/misc/penrose.html

  22. #18
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Je voudrais un peu revenir sur le pourquoi je trouve les automates cellulaires très "dérangeants".

    Etre face à un phénomène naturel que l'on ne peut pas modéliser de façon satisfaisante n'est pas un problème. Ce n'est pas une oeuvre humaine et c'est déjà bien miraculeux de pouvoir comprendre un peu.

    Par contre être face à 20 lignes de code, exécuté sur une machine dont le fonctionnement n'a rien de mystérieux et être incapable de prédire de façon satisfaisante le comportement du système, je trouve ça vraiment étonnant. Et si déjà là on bloque, que pensez de notre capacité à modéliser la nature ?

    J'ai une question sur la notion de calculabilité. Je ne connais vraiment pas bien cette notion, peut être que ma question peut paraitre bête. Est - ce que PI est calculable ? Je dirais non, puisque la connaissance de ce nombre ne peut pas se faire en un nombre fini d'étapes.

  23. Publicité
  24. #19
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par mtheory
    Exact!Et c'est vrai que lui et sa famille ne sont pas des gens très sérieux ni bien malin.
    La preuve:

    http://www-gap.dcs.st-and.ac.uk/~his...s/Penrose.html

    http://www.worldofescher.com/misc/penrose.html
    Argument d'autorité, ça ne nous avance pas beaucoup

  25. #20
    pi-r2

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Pi est calculable parce que les algorithmes qui permettent de calculer Pi s'écrivent en un nombre fini d'instructions. C'est d'après ce que j'en ai compris la définition de la calculabilité. C'est une forme de compression d'information. Le fait qu'il faille faire tourner l'algorithme pendant une durée infinie pour avoir une infinité de décimale ne rend pas le nombre non calculable.
    Maintenant, en fait il faudrait établir plutot des degrés de calculabilité de incalculable (ou incompressible) à très simple.
    Les bonnes idées triomphent toujours... C'est à cela qu'on reconnait qu'elles étaient bonnes !

  26. #21
    pi-r2

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par spi100
    Etre face à un phénomène naturel que l'on ne peut pas modéliser de façon satisfaisante n'est pas un problème. Ce n'est pas une oeuvre humaine et c'est déjà bien miraculeux de pouvoir comprendre un peu.

    Par contre être face à 20 lignes de code, exécuté sur une machine dont le fonctionnement n'a rien de mystérieux et être incapable de prédire de façon satisfaisante le comportement du système, je trouve ça vraiment étonnant. Et si déjà là on bloque, que pensez de notre capacité à modéliser la nature ?
    .
    Pour revenir sur ce que tu dis, si tu renverses le point de vue: l'informatique nous offre alors grace à ces 20 lignes de code un super modèle bien maitrisable et bien encadré pour comprendre. N'est-ce pas le rêve de tout physicien d'avoir un univers simple à étudier à sa disposition. C'est là que les travaux de Wolfram deviennent plus intéressants et plus proche de la physique qu'on ne le pense au premier abord.
    L'informatique est un excellent modèle pour se forger cette nouvelle intuition qui nous aidera à comprendre la complexité.
    Les bonnes idées triomphent toujours... C'est à cela qu'on reconnait qu'elles étaient bonnes !

  27. #22
    JPL
    Responsable des forums

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Je crois que Mtheory veut parler de Roger Penrose, un dangereux spiritualiste
    Roger Penrose est d'abord un grand mathématicien, mondialement connu. Qu'il ait des convictions spiritualistes n'en fait pas, pour ce simple motif, un individu dangereux, ou alors tu méprises tous ceux qui n'ont pas les mêmes convictions que toi. Et alors tu dois admettre qu'il pourrait dire de façon également légitime que x ou y, ou spi100 est un dangereux matérialiste.
    Par contre tu peux discuter les arguments qu'il donne dans le livre cité.
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  28. #23
    mtheory

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Bonsoir jpl.Je suis persuadé que spi100 à le même profond respect du Grand Roger que moi ou toi c'était juste pour rire entre lui et moi.
    Il est certainement conscient des arguments de Penrose afin d'établir le caractère non algorithmique de la conscience humaine.
    Qu'il y adhère ou pas est un autre problème sur lequel lui seul peut répondre.
    C'est vrai que le livre de Penrose est très bon.

  29. #24
    Lambda0

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Pi_r2
    "D'abord pour bien clarifier les choses, il n'y a pas de différence de possibilités entre une machine de turing, un réseau neuronal à nombre fini de neurones ou un automate cellulaire fini. Ils sont équivalents du point de vue de la calculabilité.
    Pour la calculabilité de l'univers j'ose une petite démonstration: Le programme capable de calculer l'univers est par restriction capable de calculer le résultat de tout algorithme tournant sur une machine de Turing. Ce 'programme' serait donc d'une 'classe' supérieure et au moins équivalent à un réseau infini (pas aussi grand qu'on le veut, infini). Donc l'univers n'est pas calculable. Il ne peut pas non plus être restreint à une série de lois physiques calculables: il restera toujours de l'imprévu, imprévisible."

    => bien vu. Je ne me serais pas mieux exprimé. Ce serait bien sûr à formaliser un peu, par quelqu'un maitrisant la théorie de la calculabilité.
    Mon propos dans cette discussion est justement d'"exhiber" des contradictions logiques qui feraient que l'univers n'est pas calculable, indépendamment de tout argument physique qui viendrait encore renforcer ce fait.

  30. Publicité
  31. #25
    Lambda0

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Spi100
    D'accord sur le fait que les automates cellulaires sont plus pratiques à manipuler concrètement. Je préférais raisonner sur la machine de Turing parce qu'il s'agit d'un objet plus élémentaire.
    Mais je ne suis en fait pas très à l'aise dans cette discussion et j'en reviens à ce que j'ai pointé au début : il nous manque un mathématicien familier avec ces notions de calculabilité.
    (arghh j'ai relancé un débat que je n'ai pas les moyens de soutenir).

    Mtheory
    Non, réellement. J'ai bien déjà entendu le nom mais je ne connais pas les théories de Penrose. D'ailleurs, je ne suis pas mathématicien.

  32. #26
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par JPL
    Roger Penrose est d'abord un grand mathématicien, mondialement connu. Qu'il ait des convictions spiritualistes n'en fait pas, pour ce simple motif, un individu dangereux, ou alors tu méprises tous ceux qui n'ont pas les mêmes convictions que toi.
    C'est un des rares scientifiques a défendre le point de vue spiritualiste, et dans le sens où effectivement il est aussi l'un des rares à le faire intelligemment, il est dangereux.
    C'était de l'humour , ça me semblait vraiment évident, désolé si cela t'a outré.
    Dernière modification par spi100 ; 02/09/2004 à 11h13.

  33. #27
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par pi-r2
    Pour revenir sur ce que tu dis, si tu renverses le point de vue: l'informatique nous offre alors grace à ces 20 lignes de code un super modèle bien maitrisable et bien encadré pour comprendre. N'est-ce pas le rêve de tout physicien ... L'informatique est un excellent modèle pour se forger cette nouvelle intuition qui nous aidera à comprendre la complexité.
    Oui, c'est bien pour ça que je me passionne pour ce sujet depuis pas mal d'années. En créant ce fil, j'espérais aider à comprendre que 'algorithme' n'est pas synonyme de 'prévisiblité' et de 'maîtrise totale'.
    Dernière modification par spi100 ; 02/09/2004 à 11h25.

  34. #28
    mtheory

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Dans le genre plus 'correct' il y a eut un autre monstre qui m'as toujours beaucoup impressionné ,Stanislas Ulam, qui a fait des travaux de pionner sur les automates cellulaires,le chaos,les systèmes non linéaires.
    Voici une bonne référence:
    http://www-users.cs.york.ac.uk/~susa...c/ncgrntcp.htm
    et une autre plus biographique.
    http://www-gap.dcs.st-and.ac.uk/~his...ians/Ulam.html

    Ce type a travaillé dans presque toutes les branches des mathématiques et des sciences naturelles,il rivalise avec John Von neumann!

  35. #29
    mach3
    Modérateur

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Ce type a travaillé dans presque toutes les branches des mathématiques et des sciences naturelles,il rivalise avec John Von neumann!
    ils ont meme bossé ensemble

  36. #30
    spi100

    Re : programme non algorithmique : libre arbitre et hasard intrinsèque

    Citation Envoyé par Lambda0
    Ce 'programme' serait donc d'une 'classe' supérieure et au moins équivalent à un réseau infini (pas aussi grand qu'on le veut, infini).
    D'infini je n'en connais un seul, à savoir justement 'aussi grand que l'on veut'.
    Je pense que tu veux plutot parler de classe supérieure dans le même sens où l'on dit que |R est plus puissant que |N. Ainsi effectivement, lorsque l'on dit qu'un segment de |R contient une infinité de points, il en contient en fait plus que n'en contient |N, car tu ne peux pas construire de bijection entre |N et le segment. En peu plus familièrement, on peut dire que les deux contiennent une infinité de points mais le segment continu en contient encore plus que l'infini de |N.

    Est - ce vous pouvez donner des exemples de problèmes qui ne peuvent pas se réduire à un algorithme ?
    Dernière modification par spi100 ; 02/09/2004 à 13h09.

Page 1 sur 3 12 DernièreDernière

Discussions similaires

  1. libre arbitre
    Par bILLI dans le forum Epistémologie et Logique (archives)
    Réponses: 4
    Dernier message: 02/06/2007, 06h58
  2. À propos du libre arbitre
    Par The Nameless dans le forum Éthique des sciences (archives)
    Réponses: 578
    Dernier message: 13/03/2007, 16h00
  3. Le libre-arbitre
    Par verchiel dans le forum Epistémologie et Logique (archives)
    Réponses: 132
    Dernier message: 24/06/2006, 15h35
  4. Libre arbitre
    Par mach3 dans le forum Discussions scientifiques
    Réponses: 42
    Dernier message: 30/09/2005, 16h39
  5. Smullyan et le libre arbitre
    Par Nuage dans le forum Epistémologie et Logique (archives)
    Réponses: 11
    Dernier message: 22/09/2005, 21h06