|
Cahiers du Centre de Logique, vol. 11RéférencesChristian MICHAUX (éditeur), Definability in Arithmetics and Computability RésuméCe Cahier est composé de quatre articles, publiés sous la direction de Christian Michaux de l'équipe de logique de l'université de Mons-Hainaut: UMH Dans le premier de ces articles, A. Maes fait une relecture personnelle des travaux de A.L. Semenov sur certaines extensions de l'arithmétique de Presburger; il met particul\iérement en lumière la filiation des méthodes utilisées avec celles de M. Presburger dans sa célèbre preuve de la décidabilité de la théorie des nombres naturels avec l'addition. L'article suivant est une courte contribution par Th. Lavendhomme et A. Maes. Les auteurs y donnent une nouvelle preuve d'un résultat de M. Boffa sur l'indécidabilité de la théorie du premier ordre des naturels avec l'addition et un prédicat pour les nombres premiers d'une progression arithmétique. Dans le troisième article, M. Margenstern et L. Pavlotskaïa développent la notion de fonctions calculables par une machine de Turing sur un ensemble donné de mots et montrent que cette notion est très dépendante de la notion de calcul choisie, en particulier pour les machines de Turing universelles. Fr. Point, dans le dernier papier de ce volume, étudie des extensions de l'arithmétique de Presburger liées à certains systèmes de numérations. Par des méthodes modèle-théoriques, elle obtient plusieurs résultats d'élimination (relative) des quantificateurs et de décidabilité. Table des matières
|
|||||||||||||||||||||||||||||||||||
|
23 octobre 2015 |
|||||||||||||||||||||||||||||||||||
