Forwarding you to www.rutherfordjournal.org

In 1948 John von Neumann expressed the need for a theory of automata to take account of the possibilities and limits of the electronic digital computer, but he could not specify the mathematical form of such a theory might take. Over the next two decades, theoretical computer science emerged from the intersection of the research agendas of a wide range of established fields, including mathematics. By 1970 theoretical computer science had its own rubric in Mathematical Reviews , its own textbooks, and its own research agenda, and its concepts and techniques were becoming a resource for other sciences. The talk will describe the main lines of this process, which took place in two stages corresponding to a continuing division in the subject. Beginning in the late 1950s, automata theory took shape as the quasi-algebraic study of formal languages and the machines that recognize them, and of computational complexity as measured by bounded Turing machines. From the early 1960s formal semantics grew out of concern with extensible programming languages, which brought out in striking form the defining characteristic of the stored-program computer, namely that functions and values occupy the same data space. In the process, theoretical computer science gave meaning to the seemingly paradoxical notion of ‘applied abstract algebra’, as it brought the most advanced concepts of twentieth-century mathematics to bear on what has become the defining technology of our time.