Walter John Savitch is best known for discovering the complexity class NL

NL (complexity)

In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....

 (nondeterministic logarithmic space), and for Savitch's theorem

Savitch's theorem

In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, states that for any function ƒ ≥ log,...

 which defines a relationship between the NSPACE

NSPACE

In computational complexity theory, the complexity class NSPACE is the set of decision problems that can be solved by a non-deterministic Turing machine using space O, and unlimited time. It is the non-deterministic counterpart of DSPACE.Several important complexity classes can be defined in terms...

 and DSPACE

DSPACE

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a...

 complexity classes. His work in establishing complexity class

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

es has helped to create the background against which non-deterministic and probabilistic reasoning can be performed. He is also known for his creation of SavitchIn, a text reading class in the Java

Java (programming language)

Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...

 language.

Aside from his work in theoretical computer science

Theoretical computer science

Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

, Savitch has written a number of textbooks for learning to program in C/C++

C (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

, Java

Java (programming language)

Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...

, Ada, Pascal

Turbo Pascal

Turbo Pascal is a software development system that includes a compiler and an integrated development environment for the Pascal programming language running on CP/M, CP/M-86, and DOS, developed by Borland under Philippe Kahn's leadership...

 and others. He has done extensive work in the field of natural language processing

Natural language processing

Natural language processing is a field of computer science and linguistics concerned with the interactions between computers and human languages; it began as a branch of artificial intelligence....

 and mathematical linguistics. He has been focused on computational computing as it applies to genetics

Genetics

Genetics , a discipline of biology, is the science of genes, heredity, and variation in living organisms....

 and biology

Biology

Biology is a natural science concerned with the study of life and living organisms, including their structure, function, growth, origin, evolution, distribution, and taxonomy. Biology is a vast subject containing many subdivisions, topics, and disciplines...

 for over 10 years.

Savitch received his PhD in mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 from UC Berkeley in 1969. Since then he has been a professor at UCSD where he is currently a professor emeritus in the computer science department.

External links

• The UCSD home page of Walter Savitch
• Richard J. Lipton
  Richard J. Lipton
  Richard Jay "Dick" Lipton is an American computer scientist who has worked in computer science theory, cryptography, and DNA computing. Lipton is presently Associate Dean of Research, Professor, and the Frederick G...
  
  , Savitch’s Theorem. Gives a historical account on how Savitch's Theorem was discovered.