Patrick Carl Fischer (December 3, 1935 – August 26, 2011) was an American computer scientist, a noted researcher in

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

and database theory, and a target of the Unabomber..Alt URL
..

Biography

Fischer was born December 3, 1935, in St. Louis, Missouri. His father, Carl H. Fischer, became a professor of actuarial mathematics at the

University of Michigan , mottoeng = "Arts, Knowledge, Truth" , former_names = Catholepistemiad, or University of Michigania (1817–1821) , budget = $10.3 billion (2021) , endowment = $17 billion (2021)As o ...

in 1941, and the family moved to Ann Arbor, Michigan where he grew up. Fischer himself went to the University of Michigan, receiving a bachelor's degree in 1957 and an MBA in 1958. He went on to graduate studies at the

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a Private university, private Land-grant university, land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern t ...

, earning a Ph.D. in 1962 under the supervision of Hartley Rogers, Jr., with a thesis on the subject of

recursion theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has sinc ...

. After receiving his Ph.D. in 1962, Fischer joined the faculty of

Harvard University Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of high ...

as an assistant professor of

applied mathematics Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathemat ...

; his students at Harvard included Albert R. Meyer, through whom Fischer has over 250 academic descendants. as well as noted computer scientists Dennis Ritchie and Arnold L. Rosenberg. In 1965, he moved to a tenured position as associate professor of computer science at

Cornell University Cornell University is a private statutory land-grant research university based in Ithaca, New York. It is a member of the Ivy League. Founded in 1865 by Ezra Cornell and Andrew Dickson White, Cornell was founded with the intention to ...

. After teaching at the

University of British Columbia The University of British Columbia (UBC) is a public university, public research university with campuses near Vancouver and in Kelowna, British Columbia. Established in 1908, it is British Columbia's oldest university. The university ranks a ...

from 1967 to 1968 (where he met his second wife Charlotte Froese) he moved to the University of Waterloo where he became a professor of applied analysis and computer science. At Waterloo, he was department chair from 1972 to 1974. He then moved to Pennsylvania State University in 1974, where he headed the computer science department, and moved again to Vanderbilt University as department chair in 1980. He taught at Vanderbilt for 18 years, and was chair for 15 years. He retired in 1998, and died of stomach cancer on August 26, 2011 in Rockville, Maryland. Like his father, Fischer became a

fellow A fellow is a concept whose exact meaning depends on context. In learned or professional societies, it refers to a privileged member who is specially elected in recognition of their work and achievements. Within the context of higher education ...

of the Society of Actuaries. Fischer's second wife, Charlotte Froese Fischer, was also a computer science professor at Vanderbilt University and the University of British Columbia, and his brother,

Michael J. Fischer Michael John Fischer (born 1942) is a computer scientist who works in the fields of distributed computing, parallel computing, cryptography, algorithms and data structures, and computational complexity. Career Fischer was born in 1942 in Ann Arbor ...

, is a computer science professor at Yale University.

Research

Fischer's thesis research concerned the effects of different models of computation on the efficiency of solving problems. For instance, he showed how to generate the sequence of

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...

s using a one-dimensional

cellular automaton A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tess ...

, based on earlier solutions to the firing squad synchronization problem, and his work in this area set the foundation for much later work on parallel algorithms. With Meyer and Rosenberg, Fischer performed influential early research on counter machines, showing that they obeyed

time hierarchy In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, ...

and space hierarchy theorems analogous to those for Turing machines. Fischer was an early leader in the field of computational complexity, and helped establish

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

as a discipline separate from mathematics and electrical engineering. He was the first chair of SIGACT, the Special Interest Group on Algorithms and Computation Theory of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...

, which he founded in 1968. He also founded the annual Symposium on Theory of Computing, which together with the Symposium on Foundations of Computer Science is one of the two flagship conferences in

, and he served five times as chair of the conference. In the 1980s, Fischer's research interests shifted to database theory. His research in that area included the study of the

semantics Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and compu ...

of databases, metadata, and incomplete information. Fischer did important work defining the nested relational model of databases, in which the values in the cells of a relational database may themselves be relations,. and his work on the mathematical foundations of database query languages became central to the databases now used by major web servers worldwide. Fischer was also an expert in information systems and their use by educational institutions.

Unabomber

Ted Kaczynski, known as the Unabomber, was a graduate student of mathematics at the University of Michigan, where Fischer's father was a professor. In 1982, Kaczynski sent the fifth of his mail bombs to Fischer, at his Penn State address; it was forwarded to Vanderbilt, where it was opened on May 5 by Fischer's secretary, Janet Smith, who was hospitalized for three weeks after the attack. Fischer claimed not to have ever met Kaczynski, and speculated that he was targeted because he "went from pure math to theoretical computer science." Kaczynski was not apprehended until 1996, and is now serving life sentences for his crimes.

References

{{DEFAULTSORT:Fischer, Patrick C. 1935 births 2011 deaths American computer scientists Theoretical computer scientists Cellular automatists Database researchers University of Michigan College of Literature, Science, and the Arts alumni Massachusetts Institute of Technology School of Science alumni Harvard University faculty Cornell University faculty University of Waterloo faculty Pennsylvania State University faculty Vanderbilt University faculty Unabomber targets Ross School of Business alumni People from Ann Arbor, Michigan