Biography:Walter Savitch

From HandWiki
Revision as of 22:19, 3 August 2023 by MedAI (talk | contribs) (update)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Short description: American computer scientist (1943–2021)
Walter John Savitch
Born(1943-02-21)February 21, 1943
DiedFebruary 1, 2021(2021-02-01) (aged 77)
Alma materUniversity of California, Berkeley
Known forSavitch's theorem, NL
Scientific career
FieldsComputer science
InstitutionsUniversity of California, San Diego
ThesisNondeterministic Tape Bounded Turing Machines[1] (1969)
Doctoral advisorStephen Cook
Websitewww-cse.ucsd.edu/users/savitch/

Walter John Savitch (February 21, 1943 – February 1, 2021)[2] was best known for defining the complexity class NL (nondeterministic logarithmic space), and for Savitch's theorem, which defines a relationship between the NSPACE and DSPACE complexity classes. His work in establishing complexity classes has helped to create the background against which non-deterministic and probabilistic reasoning can be performed.

He also did extensive work in the field of natural language processing and mathematical linguistics. He was focused on computational complexity as it applies to genetics and biology for over 10 years.

Aside from his work in theoretical computer science, Savitch wrote a number of textbooks for learning to program in C/C++, Java, Ada, Pascal and others.

Savitch received his PhD in mathematics from University of California, Berkeley in 1969 under the supervision of Stephen Cook. Since then he was a professor at University of California, San Diego in the computer science department.

References

External links

  • Richard J. Lipton, Savitch’s Theorem. Gives a historical account on how Savitch's Theorem was discovered.