希尔伯特第十问题

✍ dations ◷ 2025-04-04 11:15:12 #丢番图方程,希尔伯特问题

希尔伯特的第十个问题,就是不定方程(又称为丢番图方程)的可解答性。这是希尔伯特于1900年在巴黎的国际数学家大会演说中,所提出的23个重要数学问题的第十题。

这个问题是问,对于任意多个未知数的整系数不定方程,要求给出一个可行的方法(verfahren),使得借助于它,通过有限次运算,可以判定该方程有无整数解。

这里德文的方法(verfahren),就是英文所谓的算法(algorithm)。对于算法的概念我们是不陌生的,例如远在古希腊时代,人们就知道可以使用辗转相除法,求两个自然数的最大公约数。还有,任给一个自然数,也存在着一个方法,在有限步骤内,可以判定这个数是不是质数。

虽然人们很早就有了算法的朴素概念,但对于到底什么是可行的计算,仍没有精确的概念。一个问题的可解与不可解究竟是什么含意,当时的人们还不得而知。然而为了研究第十问题,必须给予算法精确化的观念。这点还有赖于数理逻辑学对可计算性理论的发展,才得以实现。

不定方程是指含任意数量变元的整系数多项式方程

这里 a i 1 i 2 . . . i k {\displaystyle a_{i_{1}i_{2}...i_{k}}} 。丢番图定义可以由方程组或单个方程给出,因为方程组

等价于单个方程:

递归可枚举集可以被描述为一个集合,对其存在一种算法,对这个算法,当集合的一个成员被输入时最终会停机,但一个非成员被输入时会不确定的继续。是可计算性理论(亦即递归论)给出了算法可计算性的直觉符号的精确解释,因而使得递归可枚举性的符号具有完美的严格性。显然,丢番图集是递归可枚举的。因为可以排列所有可能的未知数的值的多元组为一个序列,然后对于一个给定的参数值,一个接一个的测试这些多元组,看他们是否是相应方程的解。希尔伯特第十问题的不可解性源于令人惊讶的事实──其逆命题成立:

这一结果即马季亚谢维奇定理(由他提供的完成证明的关键步骤)和MRDP定理(即尤里·马季亚谢维奇(Yuri Matiyasevich),朱莉娅·罗宾逊(Julia Robinson),马丁·戴维斯(Martin Davis)和希拉里·普特南(Hilary Putnam)各人姓氏的首字母缩写)。因为“存在一个递归可枚举集是不可计算的”,希尔伯特第十问题的不可解性是其直接后果。实际上,还有更多的结论:有一个多项式

有整数系数使对于方程

有自然数解的 a {\displaystyle a} 的值的集合不可计算。因此,不仅没有一般的算法测试丢番图方程可解性,甚至也没有算法来测试单一参数家族的方程。

第十问题的解决是众人集体的智慧结晶。其中美国数学家马丁·戴维斯(Martin Davis)、希拉里·普特南(Hilary Putnam)和朱莉娅·罗宾逊(英语:Julia Robinson)(Julia Robinson)做出了突出的贡献。而最终的结果,是由俄国数学家尤里·马季亚谢维奇(Yuri Matiyasevich)于1970年所完成的。

其中 p {\displaystyle p} 是不定方程。他注意到丢番图集的补集并非丢番图的。而递归可枚举集对于补集运算也非封闭的,他因此猜测这两个集合类是相同的。

虽然并未成功,她发现如果存在这样的丢番图集 D = { ( a , b ) } {\displaystyle D=\{(a,b)\}} ,使得

而且

在假设这样丢番图集存在(称为J.R.)的情况下,她证明了幂函数是丢番图的。并且如果幂函数是丢番图的,那么二项式系数、阶乘以及质数集合都是丢番图的。

其中 F n {\displaystyle F_{n}} 是第 n {\displaystyle n} 个斐波那契数。也就是它是丢番图的,并满足J.R.假设。从而可构造出一个不定方程,它不是递归可解的。也就是不存在算法,可以计算该方程式的整数解。因此使得希尔伯特第十问题,得到最终否定的解答。

相关

  • 盖瑞·贝克知识产权市场化自由放任小政府主义负所得税公开市场操作私有财产私有化经济主题加里·史丹利·贝克(英语:Gary Stanley Becker,1930年12月2日-2014年5月3日),美国著名经济学家,芝加
  • 软颚挤喉音(Velar ejective)是辅音的一种,用于一些口语中。表示此音的国际音标(IPA)是⟨kʼ⟩,其等价的X-SAMPA音标则写作k_>。软颚挤喉音的特征包括:当符号成对出现时,左边的是清音
  • 苍南蛮话蛮讲,又称蛮话或蛮讲话,是中国浙江省温州市南部和东南部一带的一种方言,分为两支:一支为泰顺蛮讲,使用者居住在泰顺县;另一支为苍南蛮话,使用者居住在苍南县东北部沿海一带。泰顺蛮
  • 口诀 (朝鲜语)陶文 ‧ 甲骨文 ‧ 金文 ‧ 古文 ‧ 石鼓文 籀文 ‧ 鸟虫书 ‧ 篆书(大篆 ‧  小篆) 隶书 ‧ 楷书 ‧ 行书 ‧ 草书 漆书 ‧  书法 ‧ 飞白书笔画 
  • 瓦维洛夫拟态瓦维洛夫拟态(亦称作物拟态或杂草拟态)是植物拟态的一种形式,杂草通过一代又一代的人工选择,使自身拥有一种或多种与农作物相同的特征。 这种拟态由俄国著名植物遗传学家尼古拉
  • 情侣域名情侣域名,是情侣之间使用的一种虚拟礼品,当爱人打开情侣域名后,可以看到事先设置好的文字、图片、音乐等效果。
  • 巴西各州人类发展指数列表联合国开发计划署(UNDP)在1990年,以教育程度、收入和寿命指标,计算出衡量国家内部社会和经济发展的水平指数。最新的报告发布时间是2015,实为2014年的数据,巴西在188个国家中排名
  • 刘寿愻刘寿愻(1370年-?),字叔顺,浙江绍兴府余姚县人,民籍,明朝政治人物。同进士出身。县学生,浙江乡试第十五名。建文二年(1400年),参加庚辰科会试,得贡士第六十七名。殿试登进士三甲。曾祖父刘
  • 戴龙水戴龙水(1976年9月15日-),台湾棒球选手,守备位置为投手,1998年加入中华职棒三商虎,并获得该年度新人王,而后先后效力于统一狮及La New熊队,2005年球季控球能力明显改善,却因涉嫌职棒签
  • 人类清除计划4《人类清除计划4》(英语:)是一部2018年美国反乌托邦(英语:Utopian and dystopian fiction)动作恐怖电影,由杰拉德·麦米瑞执导,为2013年电影《人类清除计划》的前传和“人类清除计划