|
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.
|