Eastern Great Lakes Theory Workshop Talk

Turing Machine Inspired Computer Science Results

Juris Hartmanis, Cornell University

Saturday, September 29, 1:30-2:30pm

ABSTRACT

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.

Speaker Bio

Juris Hartmanis received his PhD degree in mathematics from the California Institute of Technology in 1955. After serving on the faculty at Cornell and Ohio State Universities he spent seven years as research scientist at the General Electric Research Laboratory in Schenectady, NY. In 1965 he returned to Cornell as the founding chairman of the newly created Computer Science Department and served from 1965 till 1971 and a second term from 1977 till 1982.

Hartmanis' main research interests are in theory of computing and, particularly, in computational complexity. In 1993 he shared the Turing Award with R.E. Sterns: "In recognition of their seminal paper which established the foundations for the field of computational complexity theory." For his research he was also awarded the Bolzano Gold Medal of the Academy of Sciences of the Czech Republic and the Grand Medal of the Latvian Academy of Science. He is a member of the National Academy of Engineering, American Academy of Arts and Science and Latvian Academy of Science. He holds honorary doctorates from University of Missouri and University of Dortmund. Among other current activities, he is a member of the Science Board of the Santa Fe Institute.

< Schedule < EaGL-V homepage