数论中的不可判定性 作者：bjorn poonennew

《数论中的不可判定性 作者：bjorn poonennew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数论中的不可判定性BjornPoonen方程。+。+名。=29是否有整数解?是的，例如(3，1，1)．方程z。+Y。+Z0=30怎样呢?同样有，虽然直到1999年才知道：它最小的解)是(-283059965，一2218888517，2220422932)．那么方程0+Y0+Z0：33又如何?这是一个尚未解决的问题．当然，数论并不终止于3变量3次方程的研究：我们还可以探讨1729y1093z19688一163xyzt。6。3741。6O768O0O：561．D．Hilbert(希尔伯特)在1900年著名演讲后公布所列出的23个问题中，要求听众们去寻找一种方法来回答所有这样的问题．更确切

2、地说，希尔伯特第10问题(以下记为HIO)要求一个算法，它输入一个多变量的多项式f(Xl，⋯，)，并根据是否存在整数al⋯．，a使得f(a⋯．，a)=0而输出“是”或“否”．在M．Davis，H．Putnam和J．Robinson较早工作的基础上，1970年Yu．Matiyasevich证明了这样的算法不存在．本文的目的是讨论·证明中的某些概念，·证明的一些副产品，以及·尚未解决的相关问题的研究现状，例如类似的有理数解．1．H10和DPRM定理a．算法的概念为使H10的否定回答有意义，我们需要算法的精确概念．在1900年，这样的概念还没有产生出来．但在上世纪30年代，提出了几种严格的

3、计算模型并证明是等价的；其中之一就是Turin9machine(图灵机)．这种等价性使得Church．Turin9论题是可信的，即每个纯数学的程序可以通过一个图灵机来实现．0)由此，“算法”的意思就是“图灵机”．图灵机的非正式描述也许比数学上的严格定义更有启发．一个图灵机等价于运行在一台物理上的计算机的有限长的程序，除此之外，要求这台计算机具有无限制的时间和内存，而且不受物理上错误的影响(例如电力中断引起的数据丢失)．有时候它的内存被模拟为一条无限长的磁带，初始状态为非负整数输入的二进制表示．计算机在运行期间，从内存磁带读出0和1，又写进0和1，可以根据程序规则在一条单独的输出磁带上

4、打印或不打印字符．它可以永久运行，或者在程序指定的某种条件满足时终止．译自：NoticesoftheAMS，Vo1．55(2008)，No．3，P．344350，UndecidabilityinNumberTheory,BjornPoonen．Copyright@2008theAmericanMathematicalSociety．Reprintedwithpermis—sion．Allrightsreserved．美国数学会与作者授予译文出版许可．1)由E．Pine，K．Yarbrough，W．Tarrant和M．Beck根据N．Elkies建议的途径所发现．——原注2)看来量子计

5、算机是第一个不符合这个框架的．但它们可以用经典的图灵机在指数时间内模拟，而H10问的是任何算法，不管它的运行时间、是否繁琐．当我们忘掉运行时间，那么量子计算机并不比传统的计算机更强．——原注8．对于任何对象，如果我们固定一种把这些对象变为非负整数的编码，那么图灵机就可以接受这些对象作为输入．例如，一个整系数的多项式可用它在中的字符的ASCII码)的串来表示．原来的编码是什么并不要紧，只要图灵机能够在两个编码之间转换即可．b．Diophatine(丢番图)集，可列(1istable)集和可算(computable)集Davis，Putnam，Robinson和Matiyasevich从

6、一个更强的定理推出对HIO的否定回答，这个定理有更多的重要应用．为了解释它，我们需要一些定义．定义1一个集合Az是丢番图的，如果存在多项式p(t，z)∈z[￡，1，⋯，z】使得A=a∈z：(∈z)p(a，z)=O)．我们应把P看成定义了一族依赖于参量的多项式方程；然后就是使得方程对其余变量X1⋯．，有解的那些参量值的集合．等价地，如果B是方程p(t，)=0在z+中解的集合，那么就是B在第1个坐标的投射．这个定义可以一种显然的方式扩展到Z(m>1)．例2z的子集：={0，1，2⋯．}是丢番图集，因为对a∈z，我们有a∈铮(jX1，．．．，X4∈z)；+．．．+i=a．定义3一个集合Z是

7、可列的(或可以递归地列举的)，如果存在一个算法打印出A，即一个图灵机，当它永久运行时，是其打印出来的整数集．例4可表为3个立方的整数的集合是可列集．(对所有，，10打出。+Y。+Z3；然后对所有1xl，，1Z1100打出X。+Y。+Z3；如此等等．)类似可证z的任何丢番图子集是可列的．定义5一个集合z是可算的(或递归的)，如果有一个能够决定A中成员的算法，即输入整数a，该算法能按照a是否属于A输出“是”或“否”．任何可算集是可列的，因为给出一个能够决定中成