Abstract computability: unifying complexity and computability

A benefit of abstract computability – which is the main subject matter of this talk – is that it allows the explicit unification of complexity and computability. Understanding the broader geography of these subjects is important for a number of reasons: it brings new perspectives to an old subject and it allows new tools to be brought to bear on old problems.

Abstract computability defines what one is modelling but is very flexible both on the how and the where. Of particular significance in this talk is the issue of where one models computability -- this flexibility adds a new dimension to computability. The talk demonstrates how complexity can be viewed as computability in the timed sets''. Significantly, this mimics precisely what complexity theorists actually do. The abstract approach, however, has the advantage of removing conceptual clutter and clarifying the structure of what is happening. <br><br> Abstract computability is based round the notion of a Turing category: the talk will introduce this and the necessary related structures. <br><br> References:<br> Robin Cockett, Joaquin Diaz-Boïls, Jonathan Gallagher, Pavel HrubesTimed Sets, Functional Complexity, and Computability'' Electronic Notes in Theoretical Computer Science Volume 286, 24 September 2012, Pages 117–137.

Robin Cockett, Pieter Hofstra ``Introduction to Turing Categories'' Annals of Pure and Applied Logic, Volume 156, Issues 2–3, December 2008, Pages 183–209