Mathematics and Computer Science
Putnam has contributed to scientific fields not directly related to his work in philosophy. As a mathematician, Putnam contributed to the resolution of Hilbert's tenth problem in mathematics. Yuri Matiyasevich had formulated a theorem involving the use of Fibonacci numbers in 1970, which was designed to answer the question of whether there is a general algorithm that can decide whether a given system of Diophantine equations (polynomials with integer coefficients) has a solution among the integers. Putnam, working with Martin Davis and Julia Robinson, demonstrated that Matiyasevich's theorem was sufficient to prove that no such general algorithm can exist. It was therefore shown that David Hilbert's famous tenth problem has no solution.
In computability theory, Putnam investigated the structure of the ramified analytical hierarchy, its connection with the constructible hierarchy and its Turing degrees. He showed that there exist many levels of the constructible hierarchy which do not add any subsets of the integers and later, with his student George Boolos, that the first such "non-index" is the ordinal of ramified analysis (this is the smallest such that is a model of full second-order comprehension), and also, together with a separate paper with Richard Boyd (another of Putnam's students) and Gustav Hensel, how the Davis–Mostowski–Kleene hyperarithmetical hierarchy of arithmetical degrees can be naturally extended up to .
In computer science, Putnam is known for the Davis-Putnam algorithm for the Boolean satisfiability problem (SAT), developed with Martin Davis in 1960. The algorithm finds if there is a set of true or false values that satisfies a given Boolean expression so that the entire expression becomes true. In 1962, they further refined the algorithm with the help of George Logemann and Donald W. Loveland. It became known as the DPLL algorithm. This algorithm is efficient and still forms the basis of most complete SAT solvers.
Read more about this topic: Hilary Putnam
Famous quotes containing the words computer and/or science:
“The archetype of all humans, their ideal image, is the computer, once it has liberated itself from its creator, man. The computer is the essence of the human being. In the computer, man reaches his completion.”
—Friedrich Dürrenmatt (1921–1990)
“The motive of science was the extension of man, on all sides, into Nature, till his hands should touch the stars, his eyes see through the earth, his ears understand the language of beast and bird, and the sense of the wind; and, through his sympathy, heaven and earth should talk with him. But that is not our science.”
—Ralph Waldo Emerson (1803–1882)