Davis, Martin (matematiker)

Martin Davis

Fødselsdato	1928 [1] [2] [3] […]
Fødselssted	New York , New York , USA
Land	USA
Videnskabelig sfære	talteori
Arbejdsplads	New York University
Alma Mater	Princeton University
videnskabelig rådgiver	Alonzo Kirke
Priser og præmier	Herbrand Award [d] ( 2005 ) Fellow fra American Mathematical Society medlem af American Academy of Arts and Sciences Steele-prisen ( 1975 ) Halmos-Ford-prisen [d] Guggenheim Fellowship ( 1983 )
Mediefiler på Wikimedia Commons

Martin David Davis ( eng. Martin Davis , f. 1928 ) er en amerikansk matematiker , kendt for sit arbejde med Hilberts tiende problem [4] [5] .

Biografi

Davis' forældre immigrerede til USA fra byen Lodz ( Polen ). Efter at have mødt hinanden i New York blev de gift. Davis er født og opvokset i Bronx . Martin blev opmuntret af sine forældre til at tage en videregående uddannelse [4] [5] fra barndommen .

I 1950, under vejledning af Alonzo Church , modtog Martin sin doktorgrad fra Princeton University , som er et af de ældste og mest prestigefyldte universiteter i USA.

Bidrag

Davis er en af opfinderne af Davis-Putnam-algoritmen og DPLL-algoritmen . Han er også kendt for sin postmaskinemodel .

Hilberts tiende problem

I 30'erne af det XX århundrede blev begrebet en algoritme formaliseret , og de første eksempler på algoritmisk ubeslutsomme teorier dukkede op i matematisk logik . En vigtig pointe var Andrey Markovs og Emil Posts bevis (uafhængigt af hinanden) på Thue-problemets uløselighed [6] i 1947. Dette var det første bevis på uløseligheden af et algebraisk problem. De vanskeligheder, som forskere af diophantiske ligninger står over for, har ført til den antagelse, at den algoritme , der kræves af Hilbert , ikke eksisterer. Lidt tidligere, i 1944, havde Emil Post allerede skrevet i et af sine papirer, at det tiende problem "begs for a unsolvability proof" ( Eng. "Begs for an unsolvability proof" ).

Davis hypotese

Posts ord inspirerede studerende Martin Davis til at lede efter beviser for, at det tiende problem var uløseligt. Davis flyttede fra sin formulering i heltal til en formulering i naturlige tal , hvilket er mere naturligt for teorien om algoritmer . Det er to forskellige opgaver, men hver af dem bunder i den anden. I 1953 udgav han et papir, hvori han skitserede en måde at løse det tiende problem i naturlige tal .

Davis, sammen med de klassiske diophantiske ligninger , betragtede deres parametriske version:

P(a_{1},\ldots,a_{n},x_{1},\ldots,x_{m})=0,

hvor et polynomium med heltalskoefficienter kan opdeles i to dele - parametre og variabler Med et sæt parameterværdier kan ligningen have en løsning, med et andet sæt løsninger måske ikke. Davis udpegede det sæt , der indeholder alle sæt parameterværdier ( ), som ligningen har en løsning til: $P$ $a_{1},\ldots ,a_{n}$ $x_{1},\ldots,x_{m}.$ $M$ $n$

\{a_{1},\ldots ,a_{n}\}\in M\Longleftrightarrow \exists x_{1},\ldots ,x_{m}\colon P(a_{1},\ldots, a_{n},x_{1},\ldots,x_{m})=0.

Han kaldte en sådan notation for en diofantisk fremstilling af et sæt, og selve sættet blev også kaldt diofantisk. For at bevise uløseligheden af det tiende problem, var det kun nødvendigt at vise, at ethvert numerabelt sæt er Diophantine , det vil sige at vise muligheden for at konstruere en ligning, der ville have naturlige rødder til , tilhørende dette sæt: da numerable mængder indeholder uløselige med et uløseligt sæt som grundlag, var det altså umuligt at få en generel metode, der kunne afgøre, om dette sæt ligninger har naturlige rødder. Alt dette førte Davis til følgende hypotese: $x_{1},\ldots ,x_{m}$ $\{a_{1},\ldots ,a_{n}\}$ $M$ $n$

Begreberne Diophantine og talløse sæt falder sammen. Det betyder, at et sæt er diofant, hvis og kun hvis det er talbart.

Davis tog også det første skridt - han beviste, at ethvert utalligt sæt kan repræsenteres som: $M$

\{a_{1},\ldots ,a_{n}\}\in M\Longleftrightarrow \exists z\forall y<z\exists x_{1},\ldots ,x_{m}\colon P( a_{1},\ldots,a_{n},x_{1},\ldots,x_{m},y,z)=0.

Dette er blevet kaldt "Davis normal form". På det tidspunkt lykkedes det ham ikke at bevise sin formodning ved at slippe af med den universelle kvantifier .

Priser og ærestitler

I 1975 blev Davis tildelt Steele -prisen, Chauvenet-prisen og Lester Ford-prisen for sit arbejde med Hilberts tiende problem [5] .

I 1982 blev Martin medlem af American Academy of Arts and Sciences [5] .

I 2012 blev han valgt til Fellow i American Mathematical Society [7] .

Individuelle udgaver

Bøger

Martin, Davis. Anvendt ikke-standardanalyse (neopr.) . - New York: Wiley, 1977. - ISBN 9780471198970 .
Martin, Davis; Jessica, Elaine; Ron, Segal. Beregnelighed, kompleksitet og tale: Grundlæggende om teoretisk datalogi . — 2. bind. - Boston: Academic Press, Harcourt, Brace, 1994. - ISBN 9780122063824 . (Russisk)
Martin, Davis. Logikkens motorer: matematik og computerens oprindelse . - New York: Norton, 2000. - ISBN 9780393322293 . (Russisk)

Anmeldelse af "Logic Engines": Wallace, Richard, Mathematicians Who Forget History's Fallacies: A Review of Logic Engines ("Martin Davis") , ALICE AI Foundation , < http://www.alicebot.org/articles/wallace/mathematicia .. > (utilgængeligt link) Artikler

Martin Davis (1995), "Is matematical understanding algorithmic", Behavioral and Brain Sciences, 13(4), 659-60.

Se også

Noter

↑ Martin Davis // Facetteret anvendelse af fagterminologi
↑ Martin Davis // Autoritats U.B.
↑ Martin Davis // Katalog over biblioteket ved det pavelige universitet i Saint Thomas Aquinas
↑ 1 2 Jackson, Allyn (september 2007), Interview med Martin Davis , Notices of the American Mathematical Society ( Providence, RI : American Mathematical Society ). — V. 55 ( 5 ) : 560-571 , 2008 , ISSN 0002-9920 , OCLC 1480366 .
^ 1 2 3 4 John J. O'Connor og Edmund F. Robertson . Martin Davis (engelsk) - Biografi på MacTutor- arkivet .
↑ Eksempler på uløselige problemer: slutningsproblemet i Thue-halvsystemet . Hentet 31. marts 2022. Arkiveret fra originalen 22. december 2016. (ubestemt)
↑ Liste over stipendiater fra American Mathematical Society arkiveret 13. august 2013. , hentet 2014-03-17.

Links

Martin Davis hjemmeside Arkiveret 28. september 2014 på Wayback Machine

Tematiske steder

I bibliografiske kataloger
BIBSYS: 90594044 BNC : a1121000x BNE : XX1498790 BNF : 12298096f CONOR : 46588771 GND : 116040866 ISNI : 0000 0001 0921 5209 J9U : 987007260362605171 LCCN : n50035603 LNB : 000048716 NDL : 00437365 NKC : xx0012596 NLG : 269393 NTA : 067955827 NUKAT : n98003329 SUDOC : 031840620 VIAF : 85381152 WorldCat VIAF : 85381152