Quand peut-on dire que deux algorithmes sont identiques ?

Patrick Peccatte — Tue, 25 Mar 2008 11:42:00 +0100

When Are Two Algorithms The Same? par Andreas Blass, Nachum Dershowitz, et Yuri Gurevich.

« On considère généralement que les algorithmes sont plus abstraits que les programmes qui les implémentent. La manière naturelle de formaliser cette idée est de considérer que les algorithmes constituent des classes d'équivalence de programmes selon une certaine relation d'équivalence appropriée. Nous soutenons dans cet article qu'il n'existe pas de telle relation d'équivalence. »

"Capturer" la notion intuitive d'algorithme (de façon analogue à la thèse de Church-Turing qui tente de "capturer" la notion intuitive de calculabilité) signifie être capable de proposer une définition de la relation d'équivalence qui relie deux algorithmes identiques (et pas seulement deux algorithmes qui calculent la même fonction). L'objet de l'article est de mettre en avant plusieurs difficultés concernant cette tentative et de donner des exemples qui indiquent que la notion intuitive n'est pas suffisamment bien définie pour permettre de définir une relation d'équivalence précise.
L'argument principal est que l'équivalence entre algorithmes est une notion subjective.
L'article aborde aussi des problèmes analogues comme la question de reconnaître quand deux preuves sont identiques ou deux idées sont identiques.

Lire aussi les billets sur God Plays Dice et Lambda the Ultimate.

Du bruit au signal (et inversement) - correspondance de Curry-Howard

Quand peut-on dire que deux algorithmes sont identiques ?