vu l'interet exprime par plusieurs de nous, on va mettre en place un GdT
'Quantum Computing',
en profitant de la presence de Benoit Valiron.
La premiere seance va etre mardi prochaine, le 2 Mars, a 14.30,
Chevaleret, salle 1C18
Benoit va nous introduire les outils mathematiques, et on va decider
ensemble le programme.
Les prochaines seances vont etre:
29 Mars
6 Avril
13 Avril
A bientot
Claudia Faggian
Jeudi 4 Fevrier, 11h salle 3E91
Serge Grigorieff (Liafa)
Operational algorithmic completeness of Lambda Calculus
joint work with Marie Ferbus (Liafa)
We show that lambda calculus is a computation model
which can step-by-step simulate any sequential deterministic
algorithm for any computable function over integers or words
or any datatype.
More formally, given an algorithm above a family of computable
functions (taken as primitive tools, i.e., kind of oracle
functions for the algorithm),
for every constant K big enough,
each computation step of the algorithm can be simulated
by exactly K successive reductions in a natural extension
of lambda calculus with constants for functions in the
above considered family.
The proof is based on a fixed point technique in lambda
calculus and on Gurevich Sequential Thesis which allows
to identify sequential deterministic algorithms with
Abstract State Machines.
This extends to algorithms for partial computable functions
in such a way that finite computations ending with exceptions
are associated to finite reductions leading to terms with a
particular very simple feature.
