Lời giải: Định lý MRDP: tập Diophantine chính là các tập đệ quy đếm được (1970)

Bài toán thứ mười của Hilbert, bài toán thứ mười trong hai mươi ba bài toán trong bài diễn văn năm 1900 của ông tại Đại hội Toán học Quốc tế, yêu cầu một thủ tục hữu hạn phép quyết định, với mọi đa thức $P(x_1, \ldots, x_n) \in \mathbb{Z}[x_1, \ldots, x_n]$, liệu phương trình $P(x_1, \ldots, x_n) = 0$ có nghiệm nguyên hay không. Hai đặc điểm làm yêu cầu này mạnh: thuật toán phải đồng nhất — một thủ tục duy nhất cho mọi bậc và mọi bộ hệ số — và nó phải dừng với câu trả lời có/không đúng cho mọi đầu vào, chứ không chỉ thành công trên một lớp con quyết định được.

Một số lớp con đã quyết định được. Phương trình tuyến tính $a_1 x_1 + \cdots + a_n x_n = b$ quy về tính $\gcd(a_1, \ldots, a_n)$; phương trình một biến $P(x) = 0$ quy về, sau khi khử mẫu, tính chia hết của hệ số tự do; còn phương trình bậc hai hai biến thuộc về lý thuyết dạng toàn phương nhị phân và phương trình Pell, về cơ bản được giải quyết bằng phân số liên tục. Điều mà không kỹ thuật cổ điển nào chạm được là trường hợp tổng quát, nơi một phương trình Diophantine có thể mã hóa cấu trúc số học phức tạp tùy ý và không có chặn trên số ẩn $n$.

Lời giải, hoàn thành bởi Matiyasevich năm 1970, là phủ định, và nó đòi biến từ "thủ tục" không chính thức thành một đối tượng toán học. Chứng minh dưới đây đi theo con đường được trình bày trong bài khảo sát Scholarpedia 2008 của Matiyasevich: đồng nhất tính định nghĩa được Diophantine với tính đệ quy đếm được, rồi nhập khẩu tính không quyết định được của bài toán dừng của Turing.