Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Martin Davis (mathematician)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|American mathematician (1928–2023)}} {{Use American English|date=January 2023}} {{Use mdy dates|date=January 2023}} {{Infobox mathematician | name = Martin Davis | image = Martin Davis.jpg | image_size = 200px | caption = Davis in 1996 | birth_name = Martin David Davis | birth_date = {{birth date|1928|3|8}} | birth_place = [[New York City]], U.S. | death_date = {{death date and age|2023|1|1|1928|3|8}} | death_place = [[Berkeley, California]], U.S. | fields = | workplaces = {{Plainlist| * [[Bell Labs]] * [[RAND Corporation]] * [[New York University]] * [[University of California, Berkeley]] }} | alma_mater = [[City College of New York]] ([[Bachelor of Arts|AB]])<br />[[Princeton University]] ([[PhD]]) | thesis_title = On the Theory of Recursive Unsolvability | thesis_url = <!-- (or | thesis1_url = and | thesis2_url = ) -->https://www.proquest.com/docview/304373195 | thesis_year = 1950 | doctoral_advisor = [[Alonzo Church]] | academic_advisors = | doctoral_students = {{Flatlist| * [[Moshe Koppel]] * [[Donald W. Loveland]] }} | notable_students = | known_for = {{Plainlist| * [[Davis–Putnam algorithm]] * [[DPLL algorithm]] * Work on [[Hilbert's tenth problem]] }} | author_abbrev_bot = | author_abbrev_zoo = | influences = | influenced = | awards = [[Chauvenet Prize]] (1975) | religion = | signature = <!-- (filename only) --> | footnotes = | spouse = {{Marriage|Virginia Whiteford Palmer|1951}} }} '''Martin David Davis''' (March 8, 1928 – January 1, 2023) was an American mathematician and [[computer scientist]] who contributed to the fields of [[computability theory]] and [[mathematical logic]]. His work on [[Hilbert's tenth problem]] led to the [[Diophantine set#Matiyasevich's theorem|MRDP theorem]]. He also advanced the [[Post–Turing machine|Post–Turing model]] and co-developed the [[Davis–Putnam–Logemann–Loveland algorithm|Davis–Putnam–Logemann–Loveland (DPLL) algorithm]], which is foundational for [[Boolean satisfiability problem|Boolean satisfiability solvers]]. Davis won the [[Leroy P. Steele Prize]], the [[Chauvenet Prize]] (with [[Reuben Hersh]]), and the [[Lester R. Ford]] Award. He was a fellow of the [[American Academy of Arts and Sciences]] and a fellow of the [[American Mathematical Society]]. == Early life and education == Davis's parents were Jewish immigrants to the United States from [[Łódź]], Poland<!-- DO NOT LINK, see [[MOS:GEOLINK]] for further guidance -->, and married after they met again in New York City. Davis was born in New York City on March 8, 1928. He grew up in the [[Bronx]], where his parents encouraged him to obtain a full education.<ref name="jackson">{{Citation |last=Jackson |first=Allyn |title=Interview with Martin Davis |date=September 2007 |url=https://www.ams.org/notices/200805/tx080500560p.pdf |periodical=[[Notices of the American Mathematical Society]] |volume=55 |issue=5 |pages=560–571 |publication-date=May 2008 |location=Providence, Rhode Island |publisher=[[American Mathematical Society]] |issn=0002-9920 |oclc=1480366}}.</ref><ref name="mactutor">{{MacTutor Biography|id=Davis}}</ref> He graduated from the prestigious Bronx High School of Science in 1944 and went on to receive his bachelor's degree in mathematics from [[City College of New York|City College]] in 1948 and his PhD from [[Princeton University]] in 1950.<ref name=":0">{{Cite web |title=Martin Davis – Biography |url=https://mathshistory.st-andrews.ac.uk/Biographies/Davis/ |access-date=January 8, 2023 |website=Maths History |language=en}}</ref> His doctoral dissertation, entitled ''On the Theory of Recursive Unsolvability'', was supervised by American mathematician and computer scientist [[Alonzo Church]].<ref name="jackson" /><ref name="mactutor" /><ref>{{MathGenealogy|id=8018}}</ref> == Academic career == During a research instructorship at the [[University of Illinois Urbana-Champaign|University of Illinois at Urbana-Champaign]] in the early 1950s, he joined the ''Control Systems Lab'' and became one of the early programmers of the [[ORDVAC]].<ref name="jackson" /> He later worked at [[Bell Labs]] and the [[RAND Corporation]] before joining [[New York University]].<ref name="jackson"/> During his time at the NYU, he helped set up the university's computer science department. He retired from NYU in 1996.<ref name=":0" /><ref name="jackson"/> He was later a member of visiting faculty at [[University of California, Berkeley]].<ref>{{Cite web |title=Martin Davis {{!}} Department of Mathematics at University of California Berkeley |url=https://math.berkeley.edu/people/faculty/martin-davis |access-date=January 8, 2023 |website=math.berkeley.edu}}</ref> === Hilbert's tenth problem === {{Further|Hilbert's tenth problem}} Davis first worked on Hilbert's tenth problem during his PhD dissertation, working with Alonzo Church. The theorem, as posed by the German mathematician [[David Hilbert]], asks a question: given a [[Diophantine equation]], is there an algorithm that can decide if the equation is solvable?<ref name="jackson"/> Davis's dissertation put forward a conjecture that the problem was unsolvable. In the 1950s and 1960s, Davis, along with American mathematicians [[Hilary Putnam]] and [[Julia Robinson]], made progress toward solving this conjecture. The proof of the conjecture was finally completed in 1970 with the work of Russian mathematician [[Yuri Matiyasevich]]. This resulted in the [[Diophantine set#Matiyasevich's theorem|MRDP or the DPRM theorem]], named for Davis, Putnam, Robinson, and Matiyasevich.<ref name="jackson"/> Describing the problem, Davis had earlier mentioned that he found the problem "irresistibly seductive" when he was an undergraduate and later had progressively become his "lifelong obsession".<ref name=":2">{{Cite book |url=https://link.springer.com/book/10.1007/978-3-319-41842-1 |title=Martin Davis on Computability, Computational Logic, and Mathematical Foundations |series=Outstanding Contributions to Logic |year=2016 |volume=10 |language=en |doi=10.1007/978-3-319-41842-1|isbn=978-3-319-41841-4 }}</ref> === Other contributions === Davis collaborated with Putnam, [[George Logemann]], and [[Donald W. Loveland]] in 1961 to introduce the [[Davis–Putnam–Logemann–Loveland algorithm|Davis–Putnam–Logemann–Loveland (DPLL) algorithm]], which was a [[Completeness (logic)|complete]], [[backtracking]]-based [[search algorithm]] for [[Boolean satisfiability problem|deciding the satisfiability]] of [[Propositional logic|propositional logic formulae]] in [[conjunctive normal form]], i.e., for solving the [[Boolean satisfiability problem|CNF-SAT]] problem.<ref>{{Cite web |title=Computer Science – University of Texas CS395T, Spring 2011 |url=https://www.cs.utexas.edu/users/vl/teaching/lbai/dpll.pdf}}</ref> The algorithm was a refinement of the earlier [[Davis–Putnam algorithm]], which was a [[Resolution (logic)|resolution]]-based procedure developed by Davis and Putnam in 1960.<ref>{{Cite web |title=Davis–Putnam algorithm |url=https://www.hellenicaworld.com/Science/Mathematics/en/DavisPutnamalgorithm.html |access-date=January 8, 2023 |website=hellenicaworld.com |language=en-US}}</ref><ref>{{Cite web |title=DPLL algorithm – Learning Logic for Computer Science |url=https://logic4free.informatik.uni-kiel.de/llocs/DPLL_algorithm |access-date=January 8, 2023 |website=logic4free.informatik.uni-kiel.de}}</ref> The algorithm is foundational in the architecture of fast [[Boolean satisfiability problem|Boolean satisfiability solvers.]]<ref name=":2"/> In addition to his work on [[computability theory]], Davis also made significant contributions to the fields of [[computational complexity]] and [[mathematical logic]].<ref name="jackson"/><ref name=":2"/><ref>{{Cite news |date=December 1, 2017 |title=New and Noteworthy Titles on Our Bookshelf |pages=1327 |work=[[American Mathematical Society]] - Notices of the AMS |url=https://www.ams.org/publications/journals/notices/201711/rnoti-p1327.pdf |access-date=January 7, 2023}}</ref> Davis was also known for his model of [[Post–Turing machine]]s.<ref name=":0" /> In 1974, Davis won the [[Lester R. Ford]] Award for his expository writing related to his work on Hilbert's tenth problem,<ref name="mactutor" /><ref>{{cite journal|author=Davis, Martin|title=Hilbert's tenth problem is unsolvable|journal=Amer. Math. Monthly|volume=80|issue=3|year=1973|pages=233–269|url=https://maa.org/programs/maa-awards/writing-awards/hilberts-tenth-problem-is-unsolvable|doi=10.2307/2318447|jstor=2318447}}</ref> and in 1975 he won the [[Leroy P. Steele Prize]] and the [[Chauvenet Prize]] (with [[Reuben Hersh]]).<ref name="Davis Hersh Hilbert 10th">{{cite journal |last1=Davis |first1=Martin |last2=Hersh |first2=Reuben |year=1973 |title=Hilbert's 10th Problem |journal=Scientific American |publisher=Springer Science and Business Media LLC |volume=229 |issue=5 |pages=84–91 |bibcode=1973SciAm.229e..84D |doi=10.1038/scientificamerican1173-84 |issn=0036-8733}}</ref> He became a [[fellow]] of the [[American Academy of Arts and Sciences]] in 1982,<ref name="mactutor"/> and in 2013, he was selected as one of the inaugural fellows of the [[American Mathematical Society]].<ref>[https://www.ams.org/profession/fellows-list List of Fellows of the American Mathematical Society]. Retrieved March 17, 2014.</ref> Davis's 1958 book ''Computability and Unsolvability'' is considered a classic in [[theoretical computer science]], while his 2000 book ''The Universal Computer'' traces the evolution and history of computing starting including works of [[Gottfried Wilhelm Leibniz]] and [[Alan Turing]].<ref name="jackson"/> His book ''The Undecidable'', the first edition of which was published in 1965, was a collection of [[unsolvable problem]]s and [[computable function]]s.<ref name=":2"/> == Personal life and death == Davis was married to Virginia Whiteford Palmer, a textile artist. The couple met during their time in the [[Urbana–Champaign]] area and subsequently married in 1951.<ref>Omodeo, E. G., & Policriti, A., eds., ''Martin Davis on Computability, Computational Logic, and Mathematical Foundations'' ([[Berlin]]/[[Heidelberg]]: [[Springer Science+Business Media|Springer]], 2016), [https://books.google.com/books?id=GlgLDgAAQBAJ&pg=PA8&redir_esc=y#v=onepage&q&f=false p. 8].</ref>{{rp|8}} They had two children.<ref name=":0" /> The couple lived in [[Berkeley, California]], after his retirement.<ref name="jackson"/> Davis died on January 1, 2023, at age 94.<ref>{{cite web |title=Martin David Davis |url=https://www.harrisfuneralhomeberkeley.com/obituaries/Martin-Davis-6/#!/TributeWall |access-date=January 4, 2023 |website=Harris Funeral Home}}</ref> His wife died the same day several hours later.<ref>{{cite web|title=Remembering Martin and Virginia Davis|url=https://www.digitalfieldguide.com/blog/20341|access-date=January 8, 2023}}</ref> == Selected publications == '''Books''' * {{cite book | last = Davis | first = Martin | title = Computability and Unsolvability | publisher = Dover| location = New York | year = 1958 | isbn = 0-486-61471-9}} [https://books.google.com/books?id=mCc3DwAAQBAJ&printsec=frontcover&source=gbs_ge_summary_r&redir_esc=y#v=onepage&q&f=false1982 Dover reprint] * {{cite book | last = Davis | first = Martin | title = Applied nonstandard analysis | url = https://archive.org/details/appliednonstanda0000davi | url-access = registration | publisher = Wiley | location = New York | year = 1977 | isbn = 9780471198970 }} [https://books.google.com/books?id=0yP0AwAAQBAJ 2014 Dover reprint] * {{cite book | last1 = Davis | first1 = Martin | last2 = Weyuker | first2 = Elaine J. | last3 = Sigal | first3 = Ron | author-link2 = Elaine Weyuker | title = Computability, complexity, and languages: fundamentals of theoretical computer science | publisher = Academic Press, Harcourt, Brace | location = Boston | year = 1994 | edition = 2nd | isbn = 9780122063824 | url=https://books.google.com/books?id=dSHIIx0uGx0C}} * {{cite book | last = Davis | first = Martin | title = The Universal Computer: The Road from Leibniz to Turing | publisher = Norton | year = 2000 | isbn = 0393047857}} Reprinted as {{cite book |title=Engines of Logic: Mathematicians and the Origin of the Computer |publisher=Norton |location=New York |year=2000 |isbn=9780393322293}} * {{Cite book |last=Davis |first=Martin |url=https://www.worldcat.org/oclc/53840050 |title=The Undecidable : Basic papers on undecidable propositions, unsolvable problems and computable functions |date=2004 |publisher=Dover Publications |isbn=0-486-43228-9 |edition= |location=New York |oclc=53840050}} '''Articles''' * Davis, Martin (1973), [https://www.math.umd.edu/~laskow/Pubs/713/Diophantine.pdf "Hilbert's Tenth Problem is Unsolvable"], ''[[The American Mathematical Monthly]]'', '''80'''(3), 233–269. {{doi|10.1080/00029890.1973.11993265}}. * Davis, Martin (1995), "Is mathematical insight algorithmic?", ''[[Behavioral and Brain Sciences]]'', '''13'''(4), 659–60. * Davis, Martin (2020), [https://books.google.com/books?id=NjTnDwAAQBAJ&pg=PA105&redir_esc=y#v=onepage&q&f=false "Seventy Years of Computer Science"], In: [[Andreas Blass|Blass A.]], Cégielski P., [[Nachum Dershowitz|Dershowitz N.]], Droste M., Finkbeiner B. (eds.) ''Fields of Logic and Computation III'', 105–117. Lecture Notes in Computer Science, vol. 12180. Springer: Cham, Switzerland. {{doi|10.1007/978-3-030-48006-6_8}}. == See also == * [[Criticism of non-standard analysis]] * [[Halting problem]] * [[Influence of non-standard analysis]] == References == {{reflist|30em}} == External links == {{Wikiquote}} * {{official website}} * [https://www.youtube.com/watch?t=5941&v=ultMxODJE7o Celebrating Emil Post & His "Intractable Problem" of Tag: 100 Years Later] on YouTube, including contributions by Martin Davis (from 1 hour 39 minutes in the recording) * {{YouTube|id=ZVTgtODX0Nc|title=Martin Davis: Universality is Ubiquitous (Princeton Academics)}} * {{cite journal|title=In Memory of Martin Davis|journal=[[Notices of the American Mathematical Society]]|date=August 2024|volume=71|issue=7|pages=898–907|url=https://www.ams.org/journals/notices/202407/rnoti-p898.pdf|doi=10.1090/noti2982|doi-access=free |last1=Calvert |first1=Wesley |last2=Harizanov |first2=Valentina |authorlink2=Valentina Harizanov |last3=Omodeo |first3=Eugenio G. |last4=Policriti |first4=Alberto |last5=Shlapentokh |first5=Alexandra }} {{Chauvenet Prize recipients}} {{Authority control}} {{DEFAULTSORT:Davis, Martin}} [[Category:1928 births]] [[Category:2023 deaths]] [[Category:20th-century American Jews]] [[Category:20th-century American mathematicians]] [[Category:21st-century American Jews]] [[Category:21st-century American mathematicians]] [[Category:American logicians]] [[Category:American people of Polish-Jewish descent]] [[Category:Courant Institute of Mathematical Sciences faculty]] [[Category:Fellows of the American Academy of Arts and Sciences]] [[Category:Fellows of the American Mathematical Society]] [[Category:Institute for Advanced Study visiting scholars]] [[Category:New York University faculty]] [[Category:American number theorists]] [[Category:Princeton University alumni]] [[Category:Scientists from the Bronx]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Authority control
(
edit
)
Template:Chauvenet Prize recipients
(
edit
)
Template:Citation
(
edit
)
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:Cite news
(
edit
)
Template:Cite web
(
edit
)
Template:Doi
(
edit
)
Template:Further
(
edit
)
Template:Infobox mathematician
(
edit
)
Template:MacTutor Biography
(
edit
)
Template:MathGenealogy
(
edit
)
Template:Official website
(
edit
)
Template:Reflist
(
edit
)
Template:Rp
(
edit
)
Template:Short description
(
edit
)
Template:Use American English
(
edit
)
Template:Use mdy dates
(
edit
)
Template:Wikiquote
(
edit
)
Template:YouTube
(
edit
)