Personal tools
You are here: Home Events Abstract Archives 2006-2007 Fast exhaustive search over infinite search spaces.

Fast exhaustive search over infinite search spaces.

Martin Escardo University of Birmingham 4pm Tuesday 5th September 2006 Room 2511, JCMB, King's Buildings

It is known that there are infinite sets that admit exhaustive search in finite time. The aim of this talk is to (1) make this surprising fact available to a more general audience, (2) develop new results about the nature of mechanically exhaustible sets, and (3) perform first steps about the efficiency of exhaustive search over infinite sets. Regarding (2), we show that exhaustible sets are closed under computable images and finite and countable products, giving meaningful examples, and, regarding (3), we discuss instances of exhaustive searches that defy intuition not only for being over infinite sets, but also for being faster than one would expect, briefly indicating what is behind this unexpected behaviour. We also indicate potential applications to automatic program verification and model checking.

Document Actions