Turing and the development of computational complexity
Date
2011-12-20
DOI
Authors
Homer, Steve
Selman, Alan
Version
OA Version
Citation
Homer, Steve; Selman, Alan. "Turing and the Development of Computational Complexity", Technical Report BUCS-TR-2011-027, Computer Science Department, Boston University, December 20, 2011. [Available from: http://hdl.handle.net/2144/11384]
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.