Мартин Дэвис: Американдық математик және компьютер ғалымы (1928–2023)
Martin Davis (mathematician)
Мартин Дэвис (1928-2023) – американ математигі, есептеу теориясы мен математикалық логикаға үлкен үлес қоскан. MRDP теоремасы, DPLL алгоритмі туралы ақпарат.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Американдық математик (1928–2023)
American mathematician (1928–2023)
Мартин Дэвид Дэвис (8 наурыз 1928 – 1 қаңтар 2023) – американдық математик және компьютерлік ғалым, есептеу теориясы және математикалық логика салаларына үлес қосып, Гилберттің оныншы мәселесі бойынша жүргізген жұмысы MRDP теоремасына әкелді. Ол сондай-ақ Пост–Тьюринг моделін дамытып, Бульдік қанағаттандыруды шешетін программалардың негізі болған Дэвис–Путнам–Логеман–Ловеланд (DPLL) алгоритмін бірлесіп жасады. Дэвис Лерой П. Стил сыйлығын, Рубен Хершпен бірге Шоувене сыйлығын және Лестер Р. Форд сыйлығын жеңіп алды. Ол Америка өнер және ғылым академиясының және Америка математикалық қоғамының мүшесі болды.
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 MRDP theorem. He also advanced the Post–Turing model and co developed the Davis–Putnam–Logemann–Loveland (DPLL) algorithm, which is foundational for 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.
Ерте өмір және білім
Дэвистің ата-анасы Польшаның Лодзь қаласынан АҚШ-қа көшіп келген еврей иммигранттары еді және олар Нью-Йорк қаласында қайта кездескеннен кейін үйленді. Дэвис 1928 жылдың 8 наурызында Нью-Йорк қаласында дүниеге келді. Ол Бронкста өсті, онда оның ата-анасы толық білім алуға ынталандырды. Ол 1944 жылы беделді Бронкс ғылым орта мектебін бітіріп, 1948 жылы Сити колледжінде математика мамандығы бойынша бакалавр дәрежесін, ал 1950 жылы Принстон университетінде докторлық дәрежесін алды. Оның докторлық диссертациясы "Рекурсивті шешілмейтін мәселелер теориясы" деп аталып, американдық математик және компьютер ғалымы Алонзо Черч басшылығымен жазылған.
Davis's parents were Jewish immigrants to the United States from Łódź, Poland, 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. 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 in 1948 and his PhD from Princeton University in 1950. His doctoral dissertation, entitled On the Theory of Recursive Unsolvability, was supervised by American mathematician and computer scientist Alonzo Church.
Академиялық мансап
1950 жылдардың басында Иллинойс университетінің Урбана-Шампейн қаласындағы ғылыми-зерттеу оқытушысы қызметін атқағанда, ол Басқару жүйелері зертханасына қатысып, ORDVAC компьютерінің алғашқы бағдарламашыларының бірі болды.
During a research instructorship at the 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.
Хилберттің оныншы мәселесі
Дэвис алғаш рет Хилберттің оныншы проблемасы бойынша докторлық диссертациясында Алонзо Черчпен бірге жұмыс істеді. Немец математигі Дэвид Гилберт қойған теорема мына сұраққа жауап іздейді: берілген Диофанти теңдеуі шешімге ие ме екенін анықтайтын алгоритм бар ма?
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?
Басқа салымдар
1961 жылы Дэвис Путнам, Джордж Логеман және Дональд В. Лавлендпен бірлесіп, Дэвис–Путнам–Логеман–Лавленд (DPLL) алгоритмін ұсынды. Бұл алгоритм – конъюнктивті нормалды формадағы логикалық формулалардың қанағаттандырылуын анықтауға арналған толық, кері іздеуге негізделген іздеу алгоритмі, яғни CNF SAT мәселесін шешуге арналған. Алгоритм 1960 жылы Дэвис және Путнам жасаған шешімге негізделген процедура болған бұрынғы Дэвис–Путнам алгоритмінің жетілдірілген нұсқасы еді. Алгоритм жылдам бульдік қанағаттандырушыларды (Boolean satisfiability solvers) құру архитектурасының негізі болып табылады. Дэвис сонымен қатар Пост–Тьюринг машиналарының моделін жасауымен де белгілі болды. 1975 жылы ол Лерой П. Стил сыйлығы мен Шовене сыйлығын (Рубен Хершпен бірге) жеңіп алды. 1982 жылы Америка өнер және ғылым академиясының мүшесі атанды.
Davis collaborated with Putnam, George Logemann, and Donald W. Loveland in 1961 to introduce the Davis–Putnam–Logemann–Loveland (DPLL) algorithm, which was a complete, backtracking based search algorithm for deciding the satisfiability of propositional logic formulae in conjunctive normal form, i. e. for solving the CNF SAT problem. The algorithm was a refinement of the earlier Davis–Putnam algorithm, which was a resolution based procedure developed by Davis and Putnam in 1960. The algorithm is foundational in the architecture of fast Boolean satisfiability solvers. Davis was also known for his model of Post–Turing machines. and in 1975 he won the Leroy P. Steele Prize and the Chauvenet Prize (with Reuben Hersh). He became a fellow of the American Academy of Arts and Sciences in 1982,
Дэвистің 1958 жылғы «Есептеу мүмкіндігі және шешілмейтін мәселелер» кітабы теориялық компьютерлік ғылымдағы классикалық туынды саналады, ал 2000 жылғы «Жалпы компьютер» кітабы Готфрид Вильгельм Лейбниц және Алан Тьюрингтің еңбектерінен бастап, есептеудің эволюциясы мен тарихын баяндайды. Олардың екі баласы болды. Дэвис 2023 жылдың 1 қаңтарында 94 жасында дүние салды. Оның әйелі де сол күні бірнеше сағаттан кейін қайтыс болды.
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. They had two children. Davis died on January 1, 2023, at age 94. His wife died the same day several hours later.