English version
Cahiers du Centre de Logique,
vol. 11
References
Christian MICHAUX
(ed.), Definability in Arithmetics and Computability
volume 11 of the Cahiers du Centre de logique, AcademiaBruylant,
LouvainlaNeuve (Belgium), 2000, 116 pages
ISBN 28720945772
This Cahier can be ordered from the publisher AcademiaL'Harmattan.
Summary
This volume consists in four papers and is edited by Christian
Michaux of the Logic Team of the University of Mons: UMH.
In the first of these articles, A. Maes revisits A.L. Semenov's
work on some extensions of Presburger Arithmetic. He sheds a particular
light on the filiation between Semenov's methods and the celebrated
proof by Presburger that the theory of natural numbers with addition
are decidable.
The next contribution, due to Th. Lavendhomme and A. Maes,
provides a new proof of a recent result by M. Boffa on the
undecidability of Presburger Arithmetic enriched with a predicate
for the prime numbers of an arithmetical progression.
In the third paper M. Margenstern and L. Pavlotskaïa
introduce the notion of a function computable by a Turing machine
on a fixed set of words. They show that this notion is very dependent
on the notion of computation which has been chosen, in particular
for universal Turing machines.
Fr. Point, in the last contribution to this volume studies
extensions of Presburger Arithmetic closely related to numeration
systems. By modeltheoretic methods she proves several (relative)
quantifier elimination and decidability results.
Table of contents
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





