Juris Hartmanis (Cornell University)
Turing Machine Inspired Computer Science Results

In this talk we will discuss how the Turing machine model directly inspired developments in theoretical computer science (that played a very important role in helping establishing the intellectual respectability of computer science in the general scientific community). The Turing machine model was ideal for the creation of Computational Complexity theory which has grown in to an essential part of theoretical computer science and found application in other disciplines. The machine operation count was used to define Time-bounded computations and the tape squares used defined the Tape or Memory-bounded computations. The definition and exploration of the corresponding asymptotic complexity classes followed naturally. For example, the machine model was easily modified with a read-only input tape and separate read-write work tape, which revealed a rich collection of tape-bounded computational complexity classes below n-tape down to loglogn-tape (below are only non-regular languages). Many undecidability results were derived, including the beautifully simple proof of context-free language undecidability problems by linking them to push-down automata recognizing invalid Turing machine computations. A particularly important use of explicit Turing machine computations is in Cook's proof that SAT is NP complete that was followed by the development of this field by Cook, Karp and others and gave computer science the famous P=?NP problem.