Cyrill Gössi
Complexity Theory and Recursion Theory

Recursively enumerable sets and undecidable problems


This seminar handout explains fundamental questions in complexity theory in terms of recursion theory. The handout was a contribution to a seminar that focused on mathematical ideas and philosophical questions at the interface of logic and computer science.