Mesure de la complexité

 

La complexité de Birkhoff

17.04.2015 | par Jean-Paul Delahaye | 5 Commentaires

La plus grande découverte d'Alan Turing est sans doute qu'il y a une notion universelle unique de fonction calculable. Cette notion se définit avec les machines élémentaires qu'il introduisit dans son article de 1936 et qu'Alonzo Church a nommées « machines de Turing ». L'idée peut aussi se formuler de nombreuses façons différentes, par le lambda-calcul, par des systèmes d'équations, par les langages de programmation, etc. On prouve que les notions obtenues sont équivalentes ce qui conforte l'idée que la notion proposée... Lire la suite

Bitcoin et contenu en calcul

15.02.2015 | par Jean-Paul Delahaye | 3 Commentaires

Quand on examine le protocole technique du bitcoin, on tombe sur un point apparemment insignifiant qui le complique bizarrement et semble mystérieux concernant la mesure de la longueur d'une blockchain. En réalité il est important. Beaucoup plus, c'est la mise en œuvre pratique — pour la première fois semble-t-il— d'une idée théorique fondamentale de la théorie du calcul : l'idée que certaines chaînes de caractères ne peuvent résulter que d'un long calcul, autrement dit qu'elles possèdent un « contenu intrinsèque en calcul »,... Lire la suite

La complexité des petits objets

01.08.2014 | par Jean-Paul Delahaye | 2 Commentaires

Comparer deux petits objets A et B entre eux, et dire que A est plus simple que B est naturel et nous le faisons souvent sans nous poser de questions à propos de deux mots, deux images, deux jouets, deux motifs décoratifs, etc. Il se trouve que ce n'est que récemment qu'on a pu trouver une justification théorique à cette pratique. Personne ne contestera que 0000000000 (une petite séquence de 10 bits) est plus simple que 0101010101, qui elle-même est... Lire la suite

Ce qui vient au hasard est-il complexe ?

16.07.2014 | par Jean-Paul Delahaye | 6 Commentaires

La question posée est bien sûr imprécise, et nous allons en donner plusieurs interprétations qui conduiront à plusieurs réponses. Aucune n'est la réponse, mais leur ensemble est utile et répond à l'interrogation initiale d'une manière intéressante, nous apprenant quelque chose sur la surprise que nous ressentons quand nous découvrons que notre univers est riche et structuré. Que les théories du calcul et de l'information soient en mesure de proposer des réponses à de telles questions semblera étrange, c'est pourtant le... Lire la suite