Title: Turing and the Development of Computational Complexity

Author: Steve Homer and Alan Selman

Date: December 20, 2011

Abstract: 

Turing's beautiful capture of the concept of computability by the
``Turing machine" linked computability to a device with explicit steps
of operations and use of resources.  This invention led in a most
natural way to build the foundations for computational complexity.