signalement via Lambda the
Ultimate
Un récent article de Mark van Atten:
The
Development of Intuitionistic Logic
Tag - philosophie des mathématiques
jeudi 17 juillet 2008
Le développement de la logique intuitionniste
Par Patrick Peccatte le jeudi 17 juillet 2008, 21:21 - philosophie des mathématiques
mardi 25 mars 2008
Quand peut-on dire que deux algorithmes sont identiques ?
Par Patrick Peccatte le mardi 25 mars 2008, 11:42 - philosophie de l'informatique
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.
dimanche 9 mars 2008
La thèse de Church : hier, aujourd'hui, demain
Par Patrick Peccatte le dimanche 9 mars 2008, 11:44 - philosophie des mathématiques
« La thèse de Church - du nom du mathématicien Alonzo
Church - est le principe de base de la calculabilité. Dans sa forme la plus
ordinaire, elle affirme que tout traitement réalisable mécaniquement peut être
accompli par un ordinateur (plus précisément dans sa forme idéalisée qu'est une
machine de Turing). Dans une forme plus élaborée, elle affirme qu'un concept
intuitif, la calculabilité effective, coïncide avec un concept formel et
mathématique, la calculabilité, défini de plusieurs façons dont on a pu
démontrer mathématiquement qu'elles sont équivalentes. » (Wikipedia)
Colloque de philosophie de l’informatique
La thèse de Church : hier, aujourd'hui, demain
Regards croisés de philosophes et de théoriciens du calcul
Participation libre
Plus d'informations ici (intervenants et programme des exposés)
Colloque de philosophie de l’informatique
La thèse de Church : hier, aujourd'hui, demain
Regards croisés de philosophes et de théoriciens du calcul
VENDREDI 11 avril 2008 Centre
Sorbonne, amphi. Descartes
Le colloque se déroulera entre 9h30 et 18h45, amphithéâtre Descartes,
université Paris 1 (Panthéon-Sorbonne), 17 rue de la Sorbonne, 75005.
Tel qu’appréhendé par l’informatique théorique contemporaine, le calcul n’a plus guère de traits communs avec l’artefact qu’avaient proposé, au début du XXe siècle, les premières théories de la calculabilité (machines de Turing etc) et dans le contexte desquelles la fameuse « Thèse de Church » fut énoncée. Sous le regard contemporain, le calcul diffère de son ancêtre à la fois par ses propriétés (parallélisme, non déterminisme, concurrence), par la multiplicité de ses échelles (calcul sur les réels, fonctionnalité d’ordre supérieur, complexités intermédiaires) et par ses liens avec les sciences de la nature (calcul quantique, bio-calcul). Quel impact ces métamorphoses du calcul ont-elles sur l’horizon fermé, il y a soixante-dix ans, par la thèse de Church ? Qu’impliquent-elles quant à la question ouverte par la « version physique » de la thèse de Church : la nature calcule-t-elle ?
Coordination : Jean-Baptiste JoinetParticipation libre
Plus d'informations ici (intervenants et programme des exposés)
Les fondements des mathématiques
Par Patrick Peccatte le dimanche 9 mars 2008, 10:34 - philosophie des mathématiques
Conférence de Jean-Yves Girard sur Canal-U
le 17/06/2000
La "crise des fondements" s'ouvre en 1897 avec le paradoxe de Burali-Forti, une contradiction dans la toute jeune théorie des Ensembles. Parmi les solutions proposées, le "Programme de Hilbert " (~ 1925) accorde un rôle privilégié à la non-contradiction formelle. Le théorème d'incomplétude de Gödel (1931), qui réfute le programme de Hilbert, a fait le désespoir de tous ceux qui cherchaient une réponse définitive à leurs angoisses fondationnelles. Il a aussi gêné ceux qui cherchaient plus simplement à comprendre la nature des objets mathématiques. Ce n'est qu'avec le développement de l'informatique qu'ont pu se dégager de nouveaux axes de lecture, en rupture de plus en plus nette avec le réductionnisme Hilbertien.
mercredi 27 février 2008
Brouwer : point fixe et intuitionnisme
Par Patrick Peccatte le mercredi 27 février 2008, 09:44 - histoire des mathématiques
Anniversaire
« Le mathématicien néerlandais Luitzen Egbertus Jan Brouwer est né le 27 février
1881.
Il est surtout connu pour son travail en topologie, entre autres le théorème du point fixe qui porte son nom.
Il fut avec Henri Poincaré, Hermann Weyl et Arend Heyting l'un des principaux
artisans de la théorie des mathématiques intuitionnistes
.../... »
Ce courant est à l'origine des différents courants constructivistes modernes en philosophie des mathématiques.
D'après Blog à Maths