知识/定理
马蒂亚塞维奇（1970）：丢番图方程是否有整数解无通用算法——希尔伯特第 10 问题不可判定。
公式
$\{m: \exists x_1,\dots,x_k\ P(m,x_1,\dots,x_k)=0\}$ 恰为可枚举集；H10 无判定算法。
证明思路
证「丢番图集 = 可枚举集」（DPRM 定理），把停机问题归约进丢番图方程。
应用/例子
可计算性理论、逻辑；「算法边界」的又一铁证。
意义/影响
希尔伯特之问的否定回答；数论与可计算性理论的交汇。
DOXA · 数学编年史 · 知识详情
1970 ｜ 马蒂亚塞维奇 ｜ 逻辑 ｜ 突破
马蒂亚塞维奇（1970）：丢番图方程是否有整数解无通用算法——希尔伯特第 10 问题不可判定。
$\{m: \exists x_1,\dots,x_k\ P(m,x_1,\dots,x_k)=0\}$ 恰为可枚举集；H10 无判定算法。
证「丢番图集 = 可枚举集」（DPRM 定理），把停机问题归约进丢番图方程。
可计算性理论、逻辑；「算法边界」的又一铁证。
希尔伯特之问的否定回答；数论与可计算性理论的交汇。