The ten papers in this special issue arose from the conference CiE 2005: New Computational Paradigms, held at the University of Amsterdam in June, 2005. CiE 2005 was the first of a new series of conferences associated with the interdisciplinary network Computability in Europe focused on computability in theoretical computer science and mathematical logic, and ranging over a broad spectrum of research areas from the application of novel approaches to computation, through computability-theoretic aspects of physical systems to set-theoretic analyses of infinitary computing models.