Bài toán thứ mười của Hilbert

Xây dựng một thuật toán tổng quát mà, với bất kỳ phương trình Diophantus nào (phương trình đa thức với hệ số nguyên theo một hay nhiều ẩn), xác định trong hữu hạn bước liệu nó có nghiệm nguyên hay không.

Lời giải phủ định, nay gọi là định lý MRDP (Matiyasevich–Robinson–Davis–Putnam), được xây dựng qua nhiều giai đoạn. Năm 1953, Martin Davis phỏng đoán rằng mọi tập đệ quy liệt kê được các số nguyên chính là tập nghiệm của một họ phương trình Diophantus nào đó — ý tưởng then chốt cần thiết để chuyển tính bất khả quyết (từ bài toán dừng của Turing) sang lý thuyết số. Julia Robinson xác định một thành phần kỹ thuật thiết yếu: một quan hệ Diophantus có tốc độ tăng theo hàm mũ (giả thuyết JR). Năm 1961, Davis, Hilary Putnam và Robinson chứng minh một phiên bản của phỏng đoán Davis cho các phương trình Diophantus dạng mũ, quy toàn bộ bài toán về việc tìm một quan hệ tăng theo hàm mũ cụ thể mà thực sự là Diophantus (đa thức). Yuri Matiyasevich cung cấp mảnh ghép còn thiếu đó năm 1970, chỉ ra rằng dãy Fibonacci thỏa một điều kiện Diophantus, hoàn tất chứng minh và cho thấy không thuật toán nào có thể tồn tại.