English version

Cahiers du Centre de Logique, vol. 11

Références

Christian MICHAUX (éditeur), Definability in Arithmetics and Computability
volume 11 des Cahiers du Centre de logique, Academia-Bruylant, Louvain-la-Neuve (Belgique), 2000, 116 pages
ISBN 2-87209-4577-2

Ce Cahier peut être commandé auprès des éditions Academia-L'Harmattan.

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

Maes, A.

Revisiting Semenov's Results about Decidability of Extensions of Presburger Arithmetic

 

Lavendhomme, Th. Maes, A.

Note on the Undecidability of <omega; +, Pmr>

 

Margenstern, M. Pavlotskaïa, L.

On Functions Computable by Turing Machines

 

Point, Fr.

On Extensions of Presburger Arithmetic

 
     
     
     

 

17 l 16 l 15 l 14 l 13 l 12 l 10 l 9 l 8 l 7 l 6 l 5 l 4 l 3 l 2 l 1

 
 

 

 

 

7 septembre 2009