
Yuri Matiyasevich
Russian mathematician who gave the negative solution to Hilbert's tenth problem · 1947
- Born
- March 2, 1947
- Country
- Russia
- Section
- Computing
Biography
Yuri Vladimirovich Matiyasevich is a Russian mathematician, born in Leningrad (today Saint Petersburg) in 1947, best known for proving that no general method exists for deciding whether a Diophantine equation, a polynomial equation whose solutions must be whole numbers, has a solution. His result answered one of the questions David Hilbert posed to mathematicians in 1900, and it remains a central reference in mathematical logic and the theory of computation.
He showed an early talent for numbers. In his first school years in Leningrad, a teacher named Sofia Generson sparked his interest in mathematics. From 1961 he took part in the all-Russian olympiads, and in 1963 and 1964 he finished secondary school at a boarding school in Moscow specialising in mathematics and physics. In 1964 he won a gold medal at the International Mathematical Olympiad held in Moscow and joined the Mathematics and Mechanics Department of Leningrad State University without entrance exams. While still a second-year student he published two papers in mathematical logic in the proceedings of the Soviet Academy of Sciences and presented them at the International Congress of Mathematicians in 1966.
After graduating he entered graduate study at the St Petersburg branch of the Steklov Institute, a research body of the Russian Academy of Sciences. He completed his candidate thesis in 1970 and, at only 25, defended his doctoral dissertation in 1972, which contained the negative answer to Hilbert's tenth problem. Hilbert's list of 23 problems was a set of challenges he put to the mathematical community, and the tenth asked for a procedure that could decide whether any Diophantine equation has a whole-number solution. Matiyasevich's key step used Fibonacci numbers, a sequence in which each term is the sum of the two before it. He showed that certain equations could produce values growing exponentially, which completed earlier work by Julia Robinson, Martin Davis and Hilary Putnam. The combined result is known as the MRDP theorem, after the initials of its authors, and it implies that every set that a computer program can list corresponds to a Diophantine equation.
From 1974 he worked at LOMI, the Leningrad department of the Steklov Institute, first as a senior researcher and from 1980 as head of its Laboratory of Mathematical Logic. In 1995 he became a professor at the St Petersburg institute, first in software engineering and later in algebra and number theory. He was elected a corresponding member of the Russian Academy of Sciences in 1997 and a full member in 2008. He served as vice-president of the St Petersburg Mathematical Society, has led the city's mathematical olympiad since 2002, and has co-directed an annual German-Russian student school since 2003. He was also a member of the American Mathematical Society and the Association for Symbolic Logic, and he mentored several young mathematicians.
His legacy combines the best-known result of his career with a varied body of later work. In number theory he answered a 1927 question by George Polya about an infinite family of inequalities linked to the Riemann zeta function, and in graph theory he found an unexpected link between the four colour theorem and the divisibility of binomial coefficients. Honours such as the Markov Prize in 1980 and the Humboldt Research Award in 1998 recognise his career. A polynomial bearing his name is used in the study of colourings of triangulated spheres, but his name is above all tied to the negative answer that reshaped understanding of the limits of algorithms.
Main contributions
- 1966Two papers in mathematical logic presented at the International Congress of Mathematicians.
- 1970Young Mathematician Prize from the Leningrad Mathematical Society, an early recognition of his work.
- 1972Negative solution to Hilbert's tenth problem: no general method exists for deciding whether a Diophantine equation has a whole-number solution.
- 1972MRDP theorem, which states that every set a computer program can list corresponds to a Diophantine equation.
- 1980Markov Prize of the USSR Academy of Sciences for his work in mathematical logic.
- Unexpected link between the four colour theorem and the divisibility of binomial coefficients in graph theory.
Teachers and students
Studied under:
Taught:
Trivia and anecdotes
Gold in Moscow
In 1964 he won the gold medal at the International Mathematical Olympiad held in Moscow while still at secondary school.
Taking school exams at university
He entered university without entrance exams and took his secondary school diploma exams as a first-year student.
A doctorate at 25
He defended his doctoral thesis in 1972, aged 25, the same work that contained his answer to Hilbert's tenth problem.
Their contemporaries
While Yuri Matiyasevich was alive (1947–)…
Alive at the same time
Discovered or invented in those years
- 1947TransistorA semiconductor component that amplifies or switches electrical current between two terminals, depending on a signal applied to a third.
- 1957Artificial satelliteAn artificial satellite is a human-made object placed in orbit around a celestial body, usually Earth, to collect information, relay signals, or carry out a specific task.
- 1969InternetA global network of interconnected computer networks that communicate using the TCP/IP protocol suite.
- 1971EmailA network service that lets users send and receive digital messages through addressed mailboxes, much like postal mail but electronic.
- 1973Mobile phoneA handheld wireless phone that lets people make and receive calls while moving across a cellular network area.
- 1989World Wide WebA system of linked documents and resources, connected by hyperlinks and accessed over the Internet with web browsers.
Geoffrey Hinton1947 · Computing
Ron Rivest1947 · Computing
Leonard Adleman1945 · Computing
Martin Edward Hellman1945 · Computing
Steve Wozniak1950 · Computing
Bjarne Stroustrup1950 · Computing