Davis, Martin (matematikus)

Martin Davis

Születési dátum	1928 [1] [2] [3] […]
Születési hely	New York , New York , USA
Ország	USA
Tudományos szféra	számelmélet
Munkavégzés helye	New York-i Egyetem
alma Mater	Princeton egyetem
tudományos tanácsadója	Alonzo templom
Díjak és díjak	Herbrand-díj [d] ( 2005 ) Az Amerikai Matematikai Társaság tagja az Amerikai Művészeti és Tudományos Akadémia tagja Steele-díj ( 1975 ) Halmos-Ford díj [d] Guggenheim-ösztöndíj ( 1983 )
Médiafájlok a Wikimedia Commons oldalon

Martin David Davis ( eng. Martin Davis , 1928 ) amerikai matematikus , Hilbert tizedik problémájával foglalkozó munkájáról ismert [4] [5] .

Életrajz

Davis szülei Lodz városából ( Lengyelország ) vándoroltak be az Egyesült Államokba . Miután már New Yorkban találkoztak , összeházasodtak. Davis Bronxban született és nőtt fel . Martint szülei arra ösztönözték, hogy felsőfokú tanulmányokat folytasson [4] [5] gyermekkorától fogva .

1950-ben Martin Alonzo Church irányítása alatt doktorált a Princeton Egyetemen , amely az Egyesült Államok egyik legrégebbi és legrangosabb egyeteme.

Hozzájárulás

Davis a Davis-Putnam algoritmus és a DPLL algoritmus egyik feltalálója . Postagép modelljéről is ismert .

Hilbert tizedik problémája

A XX. század 30 -as éveiben formalizálták az algoritmus fogalmát, és a matematikai logikában megjelentek az algoritmikusan eldönthetetlen elméletek első példái . Fontos szempont volt Andrey Markov és Emil Post (egymástól függetlenül) bizonyítéka a Thue probléma megoldhatatlanságára [6] 1947-ben. Ez volt az első bizonyítéka egy algebrai probléma megoldhatatlanságának. A diofantini egyenletek kutatói előtt álló nehézségek ahhoz a feltételezéshez vezettek, hogy a Hilbert által igényelt algoritmus nem létezik. Valamivel korábban, 1944-ben Emil Post már azt írta az egyik dolgozatában, hogy a tizedik probléma „megoldhatatlansági bizonyítékért könyörög” ( ang . „Begs for an unsolability proof” ).

Davis hipotézis

Post szavai arra ösztönözték Martin Davis diákot, hogy bizonyítékot keressen arra vonatkozóan, hogy a tizedik probléma megoldhatatlan. Davis az egész számokban való megfogalmazásról a természetes számokban való megfogalmazásra tért át, ami természetesebb az algoritmusok elmélete számára . Ez két különböző feladat, de mindegyik a másikhoz vezet. 1953-ban publikált egy tanulmányt, amelyben felvázolta a természetes számokkal kapcsolatos tizedik probléma megoldásának módját .

Davis a klasszikus diofantusz-egyenletekkel együtt figyelembe vette azok parametrikus változatát:

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

ahol egy egész együtthatós polinom két részre - paraméterekre és változókra - osztható Egy paraméterérték-készlettel az egyenletnek lehet megoldása, egy másik megoldáshalmazzal nem. Davis kiemelte azt a halmazt , amely tartalmazza az összes paraméterérték-készletet ( ), amelyre az egyenletnek megoldása van: $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.

Az ilyen jelölést egy halmaz diofantin ábrázolásának nevezte, magát a halmazt pedig diofantinnak is nevezték. A tizedik feladat megoldhatatlanságának bizonyításához csak azt kellett megmutatni, hogy bármely megszámlálható halmaz Diofantin , azaz meg kell mutatni egy olyan egyenlet felépítésének lehetőségét, amelynek természetes gyökerei vannak ebbe a halmazba tartozó -nak : mivel a felsorolható halmazok tartalmaznak feloldhatatlant. így egy feloldhatatlan halmazt alapul véve nem lehetett olyan általános módszert kapni, amely meghatározná, hogy ennek az egyenlethalmaznak vannak-e természetes gyökerei. Mindez a következő hipotézishez vezette Davist: $x_{1},\ldots ,x_{m}$ $\{a_{1},\ldots ,a_{n}\}$ $M$ $n$

A Diophantine és a felsorolható halmazok fogalma egybeesik. Ez azt jelenti, hogy egy halmaz akkor és csak akkor diofantin, ha megszámlálható.

Davis is megtette az első lépést – bebizonyította, hogy bármely felsorolható halmaz ábrázolható így: $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.

Ezt "Davis normál formának" hívták. Akkoriban nem sikerült bebizonyítania sejtését azzal, hogy megszabadult az univerzális kvantortól .

Díjak és kitüntető címek

1975-ben Davist Steele -díjjal, Chauvenet-díjjal és Lester Ford-díjjal jutalmazták Hilbert tizedik problémájával kapcsolatos munkájáért [5] .

1982-ben Martin az Amerikai Művészeti és Tudományos Akadémia [5] tagja lett .

2012-ben az American Mathematical Society tagjává választották [7] .

Egyedi kiadások

Könyvek

Martin, Davis. Alkalmazott nem szabványos elemzés (neopr.) . - New York: Wiley, 1977. - ISBN 9780471198970 .
Martin, Davis; Jessica, Elaine; Ron, Segal. Kiszámíthatóság, összetettség és beszéd: Az elméleti számítástechnika alapjai . — 2. kötet. - Boston: Academic Press, Harcourt, Brace, 1994. - ISBN 9780122063824 . (Orosz)
Martin, Davis. A logika motorjai: matematika és a számítógép eredete . - New York: Norton, 2000. - ISBN 9780393322293 . (Orosz)

"Logic Engines" Review: 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 .. > (nem elérhető link) Cikkek

Martin Davis (1995), "Is mathematical megértése algoritmikus", Behavioral and Brain Sciences, 13(4), 659-60.

Lásd még

Jegyzetek

↑ Martin Davis // A tantárgyi terminológia fazettált alkalmazása
↑ Martin Davis // Autoritats U.B.
↑ Martin Davis // Az Aquinói Szent Tamás Pápai Egyetem könyvtárának katalógusa
↑ 1 2 Jackson, Allyn (2007. szeptember), Interjú Martin Davis -szel , 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 és Edmund F. Robertson . Martin Davis (angol) – Életrajz a MacTutor Archívumban .
↑ Példák megoldhatatlan problémákra: a következtetési probléma a Thue félrendszerben . Letöltve: 2022. március 31. Az eredetiből archiválva : 2016. december 22. (határozatlan)
↑ Az Amerikai Matematikai Társaság tagjainak listája archiválva : 2013. augusztus 13. , letöltve: 2014-03-17.

Linkek

Martin Davis webhelye Archivált : 2014. szeptember 28., a Wayback Machine

Tematikus oldalak

Bibliográfiai katalógusokban
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