Turing and the development of computational complexity
MetadataShow full item record
CitationHomer, 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]
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.