complexité

 

La complexité de Birkhoff

Publié 17.04.2015 par Jean-Paul Delahaye

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

Forcer la complexité

Publié 02.09.2013 par Jean-Paul Delahaye

Les pavages non périodiques du plan suscitent une étonnante curiosité. Pourtant certains sont très simples. Celui-ci par exemple : Pas de quoi s'extasier ! Un seul pavé rectangulaire est utilisé, un rectangle 1x2. Puisqu'aucune translation ne laisse invariant le pavage, il s'agit d'un pavage non périodique. Ce qui est étonnant et a exigé un authentique travail mathématique, c'est la découverte d'ensembles de pavés apériodiques, c'est-à-dire forçant la non périodicité : avec un tel ensemble de formes, on peut paver le... Lire la suite

Le tout est-il plus que la somme des parties ?

Publié 20.06.2013 par Jean-Paul Delahaye

J'ai toujours été agacé par la maxime «Le tout est plus que la somme de ses parties» due au grand Aristote. Elle a été commentée mille fois et presque toujours applaudie sans beaucoup de sens critique. La raison de cette agacement est que je ne voyais pas à quoi pouvait correspondre sérieusement —c'est-à-dire mathématiquement ou logiquement— ce "plus" que posséderait toujours le tout sur la somme de ses parties. Pour donner à la maxime un sens intéressant —et si possible... Lire la suite