Version française

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, Academia-Bruylant, Louvain-la-Neuve (Belgium), 2000, 116 pages
ISBN 2-87209-4577-2

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 model-theoretic 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
Online version.
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

October 23, 2015