# Yuri Matiyasevich

> 1947– · Mathematician
>
> **Recorded contribution:** Solved Hilbert's 10th problem (MRDP theorem); Diophantine equations

## How to use this dossier

Read for a causal chain, not a hero story: inherited problem → contribution → mechanism → downstream capability → limit. Then close the page and complete the reconstruction exercise from memory.

## 1. Historical orientation

Yuri Matiyasevich (born 1947) completed the proof of Hilbert's tenth problem in 1970 by showing that exponentially growing Fibonacci relations can be represented Diophantinely. Martin Davis, Hilary Putnam, and Julia Robinson had already shown that the missing bridge was an appropriate Diophantine encoding of exponential growth. Matiyasevich supplied it, yielding the MRDP theorem: every recursively enumerable set is Diophantine, so no algorithm decides whether every integer-coefficient polynomial has an integer solution. The theorem's name preserves collaboration. It concerns a general decision procedure, not whether mathematicians can solve any particular equation.

## 2. The problem inherited

Davis, Putnam, and Robinson had reduced Hilbert's problem to encoding exponential growth with polynomial equations, but that final representation was missing.

## 3. The central contribution

Matiyasevich used number-theoretic properties of Fibonacci sequences to prove exponential Diophantine definability and close the DPR program.

## 4. Reconstruct the mechanism

1. Use recurrence relations and divisibility properties of Fibonacci numbers to express rapidly growing integer behavior.
2. Show the relevant Fibonacci relation can be captured by the existence of integer solutions to polynomial equations.
3. Combine that relation with DPR closure constructions encoding recursively enumerable computations.
4. Reduce the halting-style membership question to Diophantine solvability, proving a universal solver cannot exist.

## 5. What changed downstream

- Hilbert's tenth problem over the integers received a negative solution.
- Polynomial equations became a universal representation of enumerable computation.
- Variants over the rationals and other rings became major open research directions.

## 6. Attribution, limits, and uncertainty

- Davis, Putnam, and Robinson supplied decades of essential groundwork, so 'Matiyasevich solved it alone' is inaccurate.
- Undecidability of the general problem does not prevent decision procedures for restricted polynomial classes.
- The corresponding problem over rational solutions remains open and must not be presented as settled.

## 7. Reconstruction lab

Write a search that enumerates integer tuples for a polynomial and recognizes solutions. Show why it semi-decides yes but cannot certify no in general, then map a tiny register-machine step relation into arithmetic constraints conceptually. Separate bounded evidence from the undecidable general claim.

## 8. Evidence trail

- [Yuri Matiyasevich](https://logic.pdmi.ras.ru/~yumat/) — Steklov Mathematical Institute
- [Hilbert's Tenth Problem](https://mitpress.mit.edu/9780262631581/hilberts-tenth-problem/) — MIT Press

---

*Research checked 2026-08-09. Dates, roles, and claims about living people are historical snapshots. Linked sources remain the authority; this dossier is original instructional synthesis.*