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 Timebounded computations
and the tape squares used defined the Tape or Memorybounded computations.
The definition and exploration of the corresponding asymptotic complexity
classes followed naturally. For example, the machine model was easily modified
with a readonly input tape and separate readwrite work tape, which revealed a
rich collection of tapebounded computational complexity classes below ntape
down to loglogntape (below are only nonregular languages). Many
undecidability results were derived, including the beautifully simple proof of
contextfree language undecidability problems by linking them to pushdown
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.
