The Turing machine paradigm in contemporary computing

摘要

The importance of algorithms is now recognized in all mathematical sciences,udthanks to the development of computability and computationaludcomplexity theory in the 20th century. The basic understanding of computabilityudtheory developed in the nineteen thirties with the pioneeringudwork of mathematicians like G¨odel, Church, Turing and Post. Their workudprovided the mathematical basis for the study of algorithms as a formalizedudconcept. The work of Hartmanis, Stearns, Karp, Cook and othersudin the nineteen sixties and seventies showed that the refinement of theudtheory to resource-bounded computations gave the means to explain theudmany intuitions concerning the complexity or hardness of algorithmicudproblems in a precise and rigorous framework.udThe theory has its roots in the older questions of definability, provabilityudand decidability in formal systems. The breakthrough in the nineteenudthirties was the formalisation of the intuitive concept of algorithmicudcomputability by Turing. In his famous 1936-paper, Turing [43] presenteduda model of computation that was both mathematically rigorous and generaludenough to capture the possible actions that any human computer udcould carry out. Although the model was presented well before digitaludcomputers arrived on the scene, it has the generality of describingudcomputations at the individual bit-level, using very basic control commands.udComputability and computational complexity theory are nowudfirmly founded on the Turing machine paradigm and its ramificationsudin recursion theory. In this paper we will extend the Turing machineudparadigm to include several key features of contemporary informationudprocessing systems.