seminaire PPS Jeudi 8/4

Chers tous,
prochaine seminaire PPS:

Jeudi 8 Avril, 11h salle 3E91

Nino Salibra (Univ. Venezia),

Problem 19

Abstract: The TLCA list of open problems is a list of twenty-two problems
that aims at collecting unresolved questions in the subject areas of the
TLCA (Typed Lambda Calculi and Applications) series of conferences.
Problem 19 in the TLCA list was posed by Fabio Alessi and Mariangiola
Dezani-Ciancaglini in 2002.

A closed lambda term M is easy if, for any other closed term N, the lambda
theory generated by M = N is consistent, while it is simple easy if, given
an arbitrary intersection type t, one can find a suitable pre-order on
types which allows to derive t for M. Simple easiness implies easiness.
The question whether easiness implies simple easiness constitutes Problem
19 in the TLCA list. We negatively answer the question providing a
nonempty co-r.e. (complement of a recursively enumerable) set of easy, but
non simple easy, lambda terms.