ABSTRACT

IS IT REASONABLE TO EXPECT THE LATTICE EMBEDDING PROBLEM TO BE DECIDABLE?

Manuel Lerman, Department of Mathematics, University of Connecticut,
Storrs, CT 06069-3009,E-mail: mlerman@math.uconn.edu. 

We will describe where the lattice embedding problem fits in relation to
attempts to understand the computably enumerable degrees. Our major goal
is to provide a clear intuitive understanding of the necessary and
sufficient condition for the embeddability of principally decomposable
lattices (lattices without critical triples) into the computably
enumerable degrees. This will include brief discussions of the pinball
machine model and the embedding requirements. We will describe the rules
imposed by the embedding requirements in order to ensure the success of a
pinball machine approach, and give a very general overview of the
necessity and sufficiency proof for the above class of lattices. This will
be followed by a brief description of the failed attempts to convert this
condition into an effective one, and of our thoughts on what should next
be tried. We conclude with some related open questions.