Patrick C. Fischer
Encyclopedia
Patrick Carl Fischer was an American computer scientist
, a noted researcher in computational complexity theory
and database theory
, and a target of the Unabomber.
. His father, Carl H. Fischer, became a professor of actuarial mathematics at the University of Michigan
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
, earning a Ph.D. in 1962 under the supervision of Hartley Rogers, Jr., with a thesis on the subject of recursion theory
.
After receiving his Ph.D. in 1962, Fischer joined the faculty of Harvard University
as an assistant professor of applied mathematics
; 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
, and again in 1968 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
of the Society of Actuaries
.
Fischer's second wife, Charlotte Froese Fischer
, is also a computer science professor at Vanderbilt University, and his brother, Michael J. Fischer
, is a computer science professor at Yale University.
s using a one-dimensional cellular automaton
, 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 algorithm
s. WIth Meyer and Rosenberg, Fischer performed influential early research on counter machine
s, showing that they obeyed time hierarchy 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
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
, 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 theoretical computer science
, 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
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 language
s became central to the databases now used by major web servers worldwide.
Fischer was also an expert in information system
s and their use by educational institutions.
Kaczynski was not apprehended until 1996, by which time the statute of limitations
on the 1982 bombing had expired, so he was never prosecuted for it.
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
, a noted researcher in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and database theory
Database theory
Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems....
, and a target of the Unabomber.
Biography
Fischer was born December 3, 1935, in St. Louis, MissouriSt. Louis, Missouri
St. Louis is an independent city on the eastern border of Missouri, United States. With a population of 319,294, it was the 58th-largest U.S. city at the 2010 U.S. Census. The Greater St...
. His father, Carl H. Fischer, became a professor of actuarial mathematics at the University of Michigan
University of Michigan
The University of Michigan is a public research university located in Ann Arbor, Michigan in the United States. It is the state's oldest university and the flagship campus of the University of Michigan...
in 1941, and the family moved to Ann Arbor, Michigan
Ann Arbor, Michigan
Ann Arbor is a city in the U.S. state of Michigan and the county seat of Washtenaw County. The 2010 census places the population at 113,934, making it the sixth largest city in Michigan. The Ann Arbor Metropolitan Statistical Area had a population of 344,791 as of 2010...
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
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
, earning a Ph.D. in 1962 under the supervision of Hartley Rogers, Jr., with a thesis on the subject of recursion theory
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
.
After receiving his Ph.D. in 1962, Fischer joined the faculty of Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
as an assistant professor of applied mathematics
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
; his students at Harvard included Albert R. Meyer
Albert R. Meyer
Albert Ronald da Silva Meyer is a professor of computer science at Massachusetts Institute of Technology . He has been a Fellow of the American Academy of Arts and Sciences since 1987, and he was inducted as a Fellow of the Association for Computing Machinery in 2000.Meyer's seminal works...
, through whom Fischer has over 250 academic descendants
Academic genealogy
An academic, or scientific, genealogy, organizes a family tree of scientists and scholars according to dissertation supervision relationships....
. as well as noted computer scientists Dennis Ritchie
Dennis Ritchie
Dennis MacAlistair Ritchie , was an American computer scientist who "helped shape the digital era." He created the C programming language and, with long-time colleague Ken Thompson, the UNIX operating system...
and Arnold L. Rosenberg
Arnold L. Rosenberg
Arnold Leonard Rosenberg is an American computer scientist. He is a distinguished university professor emeritus at the University of Massachusetts Amherst, and despite his retirement from UMass he continues to hold research positions at Northeastern University and Colorado State...
. In 1965, he moved to a tenured position as associate professor of computer science at Cornell University
Cornell University
Cornell University is an Ivy League university located in Ithaca, New York, United States. It is a private land-grant university, receiving annual funding from the State of New York for certain educational missions...
, and again in 1968 he moved to the University of Waterloo
University of Waterloo
The University of Waterloo is a comprehensive public university in the city of Waterloo, Ontario, Canada. The school was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles, and has since grown to an institution of more than 30,000 students, faculty, and staff...
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
Pennsylvania State University
The Pennsylvania State University, commonly referred to as Penn State or PSU, is a public research university with campuses and facilities throughout the state of Pennsylvania, United States. Founded in 1855, the university has a threefold mission of teaching, research, and public service...
in 1974, where he headed the computer science department, and moved again to Vanderbilt University
Vanderbilt University
Vanderbilt University is a private research university located in Nashville, Tennessee, United States. Founded in 1873, the university is named for shipping and rail magnate "Commodore" Cornelius Vanderbilt, who provided Vanderbilt its initial $1 million endowment despite having never been to the...
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
Stomach cancer
Gastric cancer, commonly referred to as stomach cancer, can develop in any part of the stomach and may spread throughout the stomach and to other organs; particularly the esophagus, lungs, lymph nodes, and the liver...
on August 26, 2011 in Rockville, Maryland
Rockville, Maryland
Rockville is the county seat of Montgomery County, Maryland, United States. It is a major incorporated city in the central part of Montgomery County and forms part of the Baltimore-Washington Metropolitan Area. The 2010 U.S...
.
Like his father, Fischer became a fellow
Fellow
A fellow in the broadest sense is someone who is an equal or a comrade. The term fellow is also used to describe a person, particularly by those in the upper social classes. It is most often used in an academic context: a fellow is often part of an elite group of learned people who are awarded...
of the Society of Actuaries
Society of Actuaries
The Society of Actuaries is a professional organization for actuaries based in North America. It was founded in 1949 as the merger of two major actuarial organizations in the United States: the Actuarial Society of America and the American Institute of Actuaries...
.
Fischer's second wife, Charlotte Froese Fischer
Charlotte Froese Fischer
Acad. Prof. Dr. Charlotte Froese Fischer PhD is a Canadian-American applied mathematician and computer scientist who gained world recognition for the development and implementation of the Multi-configurational Hartree-Fock approach to atomic structure calculations and for her theoretical...
, is also a computer science professor at Vanderbilt University, and his brother, Michael J. Fischer
Michael J. Fischer
Michael John Fischer is a computer scientist who works in the fields of distributed computing, parallel computing, cryptography, algorithms and data structures, and computational complexity.-Career:...
, 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 numberPrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s using a one-dimensional cellular automaton
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
, based on earlier solutions to the firing squad synchronization problem
Firing squad synchronization problem
The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active...
, and his work in this area set the foundation for much later work on parallel algorithm
Parallel algorithm
In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
s. WIth Meyer and Rosenberg, Fischer performed influential early research on counter machine
Counter machine
A counter machine is an abstract machine used in formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines...
s, showing that they obeyed time hierarchy and space hierarchy theorems analogous to those for Turing machines.
Fischer was an early leader in the field of computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
, and helped establish 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....
as a discipline separate from 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...
and electrical engineering
Electrical engineering
Electrical engineering is a field of engineering that generally deals with the study and application of electricity, electronics and electromagnetism. The field first became an identifiable occupation in the late nineteenth century after commercialization of the electric telegraph and electrical...
. He was the first chair of SIGACT, the Special Interest Group on Algorithms and Computation Theory of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
, which he founded in 1968. He also founded the annual Symposium on Theory of Computing
Symposium on Theory of Computing
STOC, the Annual ACM Symposium on Theory of Computing is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computer Machinery special interest group SIGACT.As...
, which together with the Symposium on Foundations of Computer Science
Symposium on Foundations of Computer Science
FOCS, the Annual IEEE Symposium on Foundations of Computer Science, is an academic conference in the field of theoretical computer science...
is one of the two flagship conferences 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....
, and he served five times as chair of the conference.
In the 1980s, Fischer's research interests shifted to database theory
Database theory
Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems....
. His research in that area included the study of the semantics
Semantics
Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....
of databases, metadata
Metadata
The term metadata is an ambiguous term which is used for two fundamentally different concepts . Although the expression "data about data" is often used, it does not apply to both in the same way. Structural metadata, the design and specification of data structures, cannot be about data, because at...
, 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
Relational database
A relational database is a database that conforms to relational model theory. The software used in a relational database is called a relational database management system . Colloquial use of the term "relational database" may refer to the RDBMS software, or the relational database itself...
may themselves be relations, and his work on the mathematical foundations of database query language
Query language
Query languages are computer languages used to make queries into databases and information systems.Broadly, query languages can be classified according to whether they are database query languages or information retrieval query languages...
s became central to the databases now used by major web servers worldwide.
Fischer was also an expert in information system
Information system
An information system - or application landscape - is any combination of information technology and people's activities that support operations, management, and decision making. In a very broad sense, the term information system is frequently used to refer to the interaction between people,...
s 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 had moved from pure mathematics to more applied research areas.Kaczynski was not apprehended until 1996, by which time the statute of limitations
Statute of limitations
A statute of limitations is an enactment in a common law legal system that sets the maximum time after an event that legal proceedings based on that event may be initiated...
on the 1982 bombing had expired, so he was never prosecuted for it.