Davis, Martin (matematician)

Martin Davis

Data nașterii	1928 [1] [2] [3] […]
Locul nașterii	New York , New York , SUA
Țară	STATELE UNITE ALE AMERICII
Sfera științifică	teoria numerelor
Loc de munca	Universitatea din New York
Alma Mater	Universitatea Princeton
consilier științific	Biserica Alonzo
Premii și premii	Premiul Herbrand [d] ( 2005 ) Fellow al Societății Americane de Matematică membru al Academiei Americane de Arte și Științe Premiul Steele ( 1975 ) Premiul Halmos-Ford [d] Bursa Guggenheim ( 1983 )
Fișiere media la Wikimedia Commons

Martin David Davis ( ing. Martin Davis , n. 1928 ) este un matematician american , cunoscut pentru munca sa la problema a zecea a lui Hilbert [4] [5] .

Biografie

Părinții lui Davis au emigrat în SUA din orașul Lodz ( Polonia ). După ce s-au întâlnit deja la New York , s-au căsătorit. Davis sa născut și a crescut în Bronx . Martin a fost încurajat de părinții săi să urmeze studii superioare [4] [5] încă din copilărie .

În 1950, sub îndrumarea lui Alonzo Church , Martin și-a primit doctoratul de la Universitatea Princeton , care este una dintre cele mai vechi și mai prestigioase universități din Statele Unite.

Contribuție

Davis este unul dintre inventatorii algoritmului Davis-Putnam și ai algoritmului DPLL . El este cunoscut și pentru modelul său de mașină de post .

A zecea problemă a lui Hilbert

În anii 30 ai secolului XX, conceptul de algoritm a fost oficializat , iar primele exemple de teorii indecidabile din punct de vedere algoritmic au apărut în logica matematică . Un punct important a fost demonstrarea de către Andrey Markov și Emil Post (independenți unul de celălalt) a insolubilității problemei Thue [6] în 1947. Aceasta a fost prima dovadă a insolubilității unei probleme algebrice . Dificultățile cu care se confruntă cercetătorii ecuațiilor diofantine au condus la presupunerea că algoritmul cerut de Hilbert nu există. Puțin mai devreme, în 1944, Emil Post deja scrisese într-una dintre lucrările sale că a zecea problemă „cersează o dovadă de insolvabilitate” ( ing. „Într-o dovadă de insolvabilitate” ).

Ipoteza Davis

Cuvintele lui Post l-au inspirat pe studentul Martin Davis să caute dovezi că a zecea problemă nu poate fi rezolvată. Davis a trecut de la formularea sa în numere întregi la o formulare în numere naturale , ceea ce este mai natural pentru teoria algoritmilor . Acestea sunt două sarcini diferite, dar fiecare dintre ele se rezumă la cealaltă. În 1953, a publicat o lucrare în care a schițat o modalitate de a rezolva a zecea problemă în numere naturale .

Davis, împreună cu ecuațiile diofantine clasice , au considerat versiunea lor parametrică :

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

unde un polinom cu coeficienți întregi poate fi împărțit în două părți - parametri și variabile.Cu un set de valori ale parametrilor, ecuația poate avea o soluție, cu un alt set de soluții poate nu. Davis a evidențiat mulțimea care conține toate seturile de valori ale parametrilor ( ) pentru care ecuația are o soluție: $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.

El a numit o astfel de notație o reprezentare diofantină a unui set, iar mulțimea în sine a fost numită și diofantină. Pentru a demonstra nerezolvabilitatea celei de-a zecea probleme, a fost nevoie doar să arătăm că orice mulțime enumerabilă este diofantină , adică să arătăm posibilitatea construirii unei ecuații care să aibă rădăcini naturale pentru , aparținând acestei mulțimi: întrucât mulțimile enumerabile conțin nerezolvabile. atunci, luând ca bază o mulțime nerezolvabilă, a fost imposibil să se obțină o metodă generală care să determine dacă această mulțime de ecuații are rădăcini naturale. Toate acestea l-au condus pe Davis la următoarea ipoteză: $x_{1},\ldots ,x_{m}$ $\{a_{1},\ldots ,a_{n}\}$ $M$ $n$

Conceptele de multimi diofantine si enumerabile coincid. Aceasta înseamnă că un set este diofantin dacă și numai dacă este enumerabil.

Davis a făcut și primul pas - a demonstrat că orice set enumerabil poate fi reprezentat ca: $M$

\{a_{1},\ldots,a_{n}\}\în 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.

Aceasta a fost numită „forma normală Davis”. În acel moment, el nu a reușit să -și demonstreze conjectura scăpând de cuantificatorul universal .

Premii și titluri onorifice

În 1975, Davis a fost distins cu Premiul Steele , Premiul Chauvenet și Premiul Lester Ford pentru munca sa la problema a zecea a lui Hilbert [5] .

În 1982, Martin a devenit membru al Academiei Americane de Arte și Științe [5] .

În 2012 a fost ales Fellow al Societății Americane de Matematică [7] .

Ediții individuale

Cărți

Martin, Davis. Analiză non-standard aplicată (neopr.) . - New York: Wiley, 1977. - ISBN 9780471198970 .
Martin, Davis; Jessica, Elaine; Ron, Segal. Calcul, complexitate și vorbire: elemente fundamentale ale informaticii teoretice . - al 2-lea volum. - Boston: Academic Press, Harcourt, Brace, 1994. - ISBN 9780122063824 . (Rusă)
Martin, Davis. Motoarele logicii: matematica și originile computerului . - New York: Norton, 2000. - ISBN 9780393322293 . (Rusă)

Revista „Motoare logice”: Wallace, Richard, Matematicieni care uită eroarele istoriei: o revizuire a motoarelor logice („Martin Davis”) , ALICE AI Foundation , < http://www.alicebot.org/articles/wallace/mathematicia .. > (link indisponibil) Articole

Martin Davis (1995), „Este înțelegerea matematică algoritmică”, Behavioral and Brain Sciences, 13(4), 659-60.

Vezi și

Note

↑ Martin Davis // Aplicarea fațetă a terminologiei subiectului
↑ Martin Davis // Autoritats U.B.
↑ Martin Davis // Catalogul Bibliotecii Universității Pontificale Sfântul Toma de Aquino
↑ 1 2 Jackson, Allyn (septembrie 2007), Interviu cu 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 și Edmund F. Robertson . Martin Davis (engleză) - Biografie la Arhiva MacTutor .
↑ Exemple de probleme de nerezolvat: problema de inferență în semisistemul Thue . Preluat la 31 martie 2022. Arhivat din original la 22 decembrie 2016. (nedefinit)
↑ List of Fellows of the American Mathematical Society Arhivat 13 august 2013. , preluat 2014-03-17.

Link -uri

Site-ul web Martin Davis Arhivat pe 28 septembrie 2014 la Wayback Machine

Site-uri tematice

În cataloagele bibliografice
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