Cyrill Gössi
Complexity Theory and Recursion Theory

Recursively enumerable sets and undecidable problems

Abstract

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.

Downloads