希尔伯特第十问题：一段数学发现史（丢番图，费马，希尔伯特，朱莉－罗宾逊，沃罗比约夫，马蒂亚塞维奇） Hilbert's Tenth Problem: a History of Mathematical Discovery (Diophantus, Fermat, Hilbert, Julia Robinson, Nikolay Vorob'ev, Yuri Matiyasevich) 

https://blog.csdn.net/linyt/article/details/4296663:

https://web.archive.org/web/20070208053504/http://www.goldenmuseum.com/1612Hilbert_engl.html:  

希尔伯特的演讲和他的 23 个数学问题   About Hilbert's address and his 23 mathematical problems

1900 年夏天，第二届国际数学大会在巴黎举行，全球数学家欢聚一堂。大卫 · 希尔伯特（ 1862 － 1943 ），著名的德国数学家，哥廷根大学教授，应邀在大会上作主要的演讲。 作为世界上最伟大的数学家之一，他以在代数理论和数论研究工作上的建树而闻名，特别是大会前不久在基础性研究《基础几何》中重新建立欧几里德几何的公理系统，更使他再次名声斐然。 经过长期的思考，他选择一种别开生面的方式来开展他的演讲。在演讲中，他使用 “ 数学问题 ” 来定义那些在他认为会决定下个世纪数学发展的数学问题。 In the summer of 1900 mathematicians met on the Second International Congress in Paris. David Hilbert (1862-1943), the famous German mathematician, Professor of the Goettingen University, was invited to deliver one of the main lectures. As the greatest World mathematician he became famous by his works in algebra and number theory, and shortly before the Congress resolutely, he has rebuilt an axiomatics of the Euclidean geometry in the fundamental work "Foundations of Geometry" (1899). After long doubts Hilbert chose an unusual form of the lecture. In the speech "Mathematical Problems" he decided to formulate those mathematical problems, which, in his opinion, should determine development of mathematics in the upcoming century.

1900 年国际数学大会中，希尔伯特的演讲也许是数学家们听到的演讲中最有影响力的，也是数学家的演讲中最有影响力的，更是传播数学的演讲中最有影响力的。希尔伯特提出了在下个世纪将被研究的 23 个主要的数学问题。有些涉及面广，如物理学公理化（问题 6 ），可能永远也不能完全解决。其它的，如问题 3 ，更具体和容易解决。有一些问题则是用与他预期截然相反的方法来解决的，如 连续统假设 （问题 1 ）。 Hilbert's address of 1900 to the International Congress of Mathematicians in Paris is perhaps the most influential speech ever given to mathematicians, given by a mathematician, or given about mathematics. In it, Hilbert outlined 23 major mathematical problems to be studied in the coming century. Some are broad, such as the axiomatization of physics (problem 6) and might never be considered completed. Others, such as problem 3, were much more specific and solved quickly. Some were resolved contrary to Hilbert's expectations, as the continuum hypothesis (problem 1).

希尔伯特的演讲不仅仅是一组数学问题的汇集，更重要的是他强调了他关于数学的哲学，在他哲学中提出问题的重要性。 Hilbert's address was more than a collection of problems. It outlined his philosophy of mathematics and proposed problems important to his philosophy.

尽管希尔伯特的演讲已经差不多过去了一个世纪之久，但它在现代数学上仍居重要的一席之地 : 任何醉心于数学研究的人都应该阅读（至少应选取部分阅读）它。Although almost a century old, Hilbert's address is still important and should be read (at least in part) by anyone interested in pursuing research in mathematics.

希尔伯特（ 1862-1943 ）

本文不打算详细分析希尔伯特全部的 23 个问题，我们仅选其中之一进行分析：希尔伯特第十问题。这个问题最近被俄国数学家马蒂亚塞维奇最近（ 1970 ）辉煌地解决了。为什么我们仅选取第十问题？原因之一是该问题已经解决了，其二是斐波纳契数作为此系列文章的主题，在解决这个问题时起到了决定性的作用。 In our Museum we will not analyze in detail all 23 Hilbert's problems. We will stay only to one of them: Hilbert's Tenth Problem. Its brilliant solution was made recently (1970) by the Russian mathematician Yuri Matiyasevich. Why we have selected just this Hilbert's problem? The first reason being this problem is already resolved. Secondly, being a subject of our Museum, Fibonacci numbers played an essential role in the solution of this problem.

丢番图方程  Diophantus equations

众所周知希尔伯特第十问题又称为 “ 判定丢番图方程的可解性 ” 。为追本溯源，我们要走近距今 17 个世纪之久的古代，走近古代数学家丢番图。丢番图被认为是古代最伟大的数学家，尽管我们对他所知甚少。他的创造性工作在代数历史上起到很大的作用，以致不少数学史学家都努力考证他的生卒年份。据估计，他生活在公元前 3 世纪的中期，享年 84 岁。丢番图的主要著作称为《算术》，这一基础数学宝库共有 13 卷，成为代数理论和数论发展中的里程碑。 As it is well known, Hilbert's tenth problem is called as "Determining the solvability of a Diophantus equation". To explain an essence of this problem, we should go back more then seventeen centuries into the past to the antique mathematician Diophantus. We know very little about Diophantus, which is considered the last great mathematician of antiquity. His creativity played such an important role in a history of algebra, that many historians of mathematics spent many efforts to establish the true period of his life. It is estimated, that he had lived in the middle of the 3rd century AD for a period of 84 years. Diophantus' main work is called "Arithmetics". This fundamental mathematical treasure consisting of 13 books became a turning point in development of algebra and number theory. In this book there was a final rejection of so-called "geometrical algebra" (when a solution of algebraic problem was reduced to geometrical construction with the help of dividers and ruler) and a passage to new mathematical language, the so-called "alphabetic algebra".

大约在公元前 5 世纪到公元元年期间希腊数学界出现经典几何代数无法解决的数学问题。其中最著名的三个古代数学问题分别是：倍立方问题，三等分角问题和化圆为方问题 ^{[ 注 ]} 。随后，第四个问题也加入此列，那就是：哪些边数为素数的正多边形可以通过尺规作图而成？ Already in the 5th century up to AD in the Greek mathematics there appeared mathematical problems, which cannot be resolved by means of the classic geometrical algebra. The most famous of these are the three mathematical problems of antiquity: the problems of the cube duplication, of the angle trisection, and the circle squaring. Subsequently the fourth problem was also added to these problems: to find out, what polygons with a prime number of the sides can be constructed by dividers and ruler?

[  译者注 ]  ：倍立方问题：求一立方体的棱长，使其体积是已知立方体的二倍；三等分角问题：求一角，使其角度是已知角的三分之一；化圆为方问题：求一正方形的边长，使其面积与一已知圆的相等。

就大家所知，解代数方程一直是主要的代数问题之一，许多数学问题都被归纳为代数方程。 对于数学家来说，解一次和二次方程简直是小菜一碟（任何男学生都知道解二次方程的通用计算公式）。然而，解三次方程显得比较困难。直到 16 世纪，意大利数学家费罗和塔尔塔利亚给出这种方程的通解公式。 17 和 18 世纪，代数方程最相关问题之一变成寻找解 5 次代数方程的公式。法国数学家伽罗瓦的研究工作解决了此问题，结果创立了新的代数学。 As it is known, one of the major algebraic problems has always been the solution of algebraic equations, to which many mathematical problems are reduced. The solutions to the equations of the first and second degree "in radicals" did not present any difficulties for mathematicians (any schoolboy knows the general formula for calculus of the second degree algebraic equation radicals). However, the solution of the cubic equations appeared more complicated, and the general formula for solution of such an equation "in radicals" was found only in the 16th century by the Italian mathematicians Ferro and Tartalia. One of the most relevant problems of the theory of algebraic equations in the 17th and 18th centuries became searching for a formula to solve the 5th degree algebraic equations. This research was completed by works of the French mathematician Evarist Galois and resulted in creation of the new algebra.

丢番图给本领域的发展注入了什么新思想呢？为什么他的名字直到现在没有在数学教材里降下来呢？自数学发展初期起，人们已认识了那些通过寻找代数方程的整数解就可解决的问题。其中有些方程根本没有解，如方程 2x - 2y = 1 在整数域内没有解，因为等号左边永远是偶数。还有一些存方程在有限解集，如方程 3x = 6 仅有唯一解 x=2 。最后还有一些方程存在无限个整数解。例如，让我们解方程 7x - 17y = 1:  (What new ideas did Diophantus introduce in the development of this area, and why is his name until now does not descend from pages of the mathematical tutorials? Problems that can be solved by finding solutions of algebraic equations in the domain of integer numbers are known since the very beginning of mathematics. Some of these equations do not have solutions at all. For example, the equation 2x - 2y = 1 cannot have solutions in the domain of integer numbers since its left-hand side is always an even number. Some other equations have a finite set of solutions. For example, the equation 3x = 6 has only one solution x = 2. And finally, some equations have an infinite set of integer solutions. For example, let us solve the equation 7x - 17y = 1: )

x = (17y + 1)/7 = 2y + (3y + 1)/7.

(3y+1)/7 必须是整数，标记为 z 。于是有 3y + 1 = 7z  和  x = 2y + z 。从而我们推导出来的方程 3y - 7y = -1 的系数比最初的小。再次使用 “ 降系数法 ” 得： (The number (3y + 1)/7 must be integer, let us denote it by z. Then 3y + 1 = 7z and x = 2y + z. Thus we have arrived at the equation 3y - 7z = -1 having smaller coefficients than the initial one. Let us apply our "coefficient reduction method" once more:) 

y = (7z - 1)/3 = 2z + (z - 1)/3.

(z-1)/3 必须是整数，标记为 t 。于是有 z=3t+1 ，(并且 The number (z - 1)/3 must be integer, let us denote it by t. Then z = 3t + 1, and )

y = 2z + t = 7t + 2,

x = 2y + z = 2(7t + 2) + 3t + 1 = 17t + 5.  

通过依次取 t 为 0, 1, -1, 2, -2, … ，可得到方程 7x - 17y = 1 的无限解集（而且这种方法可以获得方程的所有解）：(By taking t = 0, 1, -1, 2, -2, ... we obtain an infinite set of solutions of the equation 7x - 17y = 1 (moreover, this way we obtain all the solutions of this equation):) 

x = 5, y = 2; x = 22, y = 9; x = -12, y = -5; x = 39, y = 16; ... .

一般而言，上述的 “ 整数域上的代数方程 ” 定义为， P =0  ，其中 P 是系统为整数的多项式，包含一个，两个或多个未知数。例如 7x ² - 5xy - 3y ² + 2x + 4y - 11 = 0 和 x ³ + y ³ = z ³  。需要解决的问题是：给定方程 P (x , y , ...) = 0  ，如何判定方程在整数域内是否有解，如果有，如何高效找到所有解？这类问题称为丢番图方程 。 (In general, the above "algebraic equations in the domain of integer numbers" can be defined as P = 0, where P is a polynomial with integer coefficients and one, two or more variables (the "unknowns"). For example, 7x² - 5xy - 3y² + 2x + 4y - 11 = 0, or x³ + y³ = z³. The problem to be solved is: given an equation P(x, y, ...) = 0, how could we determine, whether it has solutions in the domain of integer numbers, and, if it does, how to find all of them efficiently? Such equations are called Diophantus equations.)

费马最后定理 ^{[ 注 ] Fermat's Last Theorem}

[ 译者注 ] ：费马最后定理在中国又称为 “ 费马大定理 ”

下一步将是考虑 3 阶丢番图方程， 4 阶等等。例如让我们考虑代数方程 x ² + y ² = z ²  并联系直角三角形的三边 x ， y 和 z ；如果自然数 x ， y 和 z 是方程的解，则称它们为 “ 毕氏三元数 ” 。自然数 3 ， 4 和 5 是一组毕氏三元数，因为 3² + 4² = 5² 。我们已经在其它文章提及，这样的三角形称为埃及三角形，古埃及人曾用它来设计卡夫拉金字塔。 The next step would be considering Diophantus equations of 3rd order, 4th order etc. For example, let's consider the algebraic equation x² + y² = z², connecting sides x, y, z of a right triangle. The natural numbers x, y and z, being solution of this equation, are called "Pythagorean triples". The numbers of 3, 4, 5 are those, because 3² + 4² = 5². We already mentioned in our Museum, that the triangle with such sides was called "sacred" or "Egyptian" and was used by the ancient Egyptians in the design of Chefren's Pyramid.

古代希腊数学家知道全部毕氏三元数可以由下面公式推导： The Ancient Greece mathematicians knew all Pythagorean triples, which can be derived from the following formulas:

x = m ² - n ² , y = 2mn , z = m ² + n ² ,

其中 m 和 n 为整数，并且 m > n > 0 。 where m and n are integers and m > n > 0.

此外，我们可以想到形如下面的丢番图方程： But we can consider Diophantus equations of the following kind:

x ³ + y ³ = z ³ , x ⁴ + y ⁴ = z ⁴ , x ⁵ + y ⁵ = z ⁵ , ... .

法国数学家费马在数学上的研究工作与丢番图方程有直接的联系。费马提出的数学思想广为人所接受，同时开创数论发展的新时期。最著名的莫过于费马最后定理，可阐述为： Mathematical research of the French mathematician Fermat have a direct relation to Diophantus equations. It is widely accepted opinion that Fermat's research started the new stage in development of number theory. The most famous of his work is Fermat's Last Theorem, which states that:

x ⁿ + y ⁿ = z ⁿ

当 n>2 时， x ， y 和 z 没有非零整数解。换言之，方程在 n > 2 的情况下没有自然数解。 has no non-zero integer solutions for x, y and z when n > 2. In other words, this equation at n > 2 has no solutions in natural numbers.

费马把该问题写在丢番图著作中某页的空白处，并写道 “…… 我已想到一个极不平凡的证明，但苦于此处空白太小而没法写下 ” 。 This equation was written by Fermat on margins of Diophantus' book, where he wrote the following addition: " ... I have discovered a truly remarkable proof which this margin is too small to contain".

从这个假设产生了最令人激动的数学领域之一，那就是费马最后定理之历史。具有讽刺意味的是，费马没有证明自己的定理，这并没有让世人感到惊讶，因为他并没有留下关于此定理的任何证明。 From this hypothesis, one of the most exciting areas of mathematics was born: the history of "Fermat's Last Theorem". Ironically nobody was surprised, that Fermat has not kept the proof of this theorem, since he also did not leave any proofs of his arithmetical theorems.

费马（ 1601-1665 ） 

许多著名的数学家，如欧拉，勒让德，加入研究费马最后定理的行列，试图寻求一般情况的方法，但仅成功地找到特殊情况的证明。因此，费马说在丢番图的《算法》书页的空白写不下他的证明，这意味着他的证明不可避免地存在错误。 Many great mathematicians, such as Euler, Legendre, Eummer, took part in trying to find a generic solution to the "Fermat's Last Theorem", but succeeded only in finding proofs for particular cases. Therefore, Fermat's statement that his proof did not fit on the margins of Diophantus' Arithmetica, suggests that his proof was inevitably wrong.

1994 年 9 月 19 日 ，长达 350 年之久的费马猜想最终由英国数学家 安德鲁 · 怀尔斯证明了。 Fermat's 350 years old hypothesis was finally proved on September 19, 1994 by English mathematician Andrew Wiles.

希尔伯特第十问题  Hilbert's Tenth Problem

到此为止，我们仍然没有解任意阶方程的一般方法。所有由最聪明的数论家发明的技巧只能用来求解非常特殊的丢番图方程，这是为什么呢 ? Until now, we still have no general method of solving an arbitrary degree Diophantus equation. All the sophisticated methods invented by smartest number theorists apply only to very specific types of equations. Why?

从 1900 年 8 月 6 日 到 12 日，第二次国际数学大会在巴黎举行。在他八月 8 号即星期三早上的演讲中，大卫 . 希尔伯特阐述了他著名的 23 个数学问题（全文在http://aleph0.clarku.edu/~djoyce/hilbert/problems.html）。 23 个问题中的第十问题如下：

10.   判定丢番图方程的可解性  

给定一个系数均为有理整数，包含任意个未知数的丢番图方程：设计一个过程，通过有限次的计算，能够判定该方程在有理数整数上是否可解。   

(From August 6th to August 12th 1900, the Second International Congress of Mathematicians took place in Paris. In his Wednesday morning lecture of August 8 David Hilbert stated his famous 23 mathematical problems for the coming XX century (see full text at http://aleph0.clarku.edu/~djoyce/hilbert/problems.html). The 10th of these 23 Hilbert's problems was the following:

10. Determining the solvability of a Diophantus equation.

Given a Diophantus equation with any number of unknowns and with rational integer coefficients: devise a process, which could determine by a finite number of operations whether the equation is solvable in rational integers.)

如果某个问题包含无限种情况，则称为大量问题 。例如判定 n 是否为素数这一问题就是大量问题，因为它必须对 n 值的无限集中的每个值进行判定。有多种算法可以解决此问题（一些方案简单，但费时较长；其余方案复杂，但费时较短）。 A problem is called a mass problem, if it contains an infinite number of cases. For example, the problem of determining whether n is a prime number, is a mass problem, since it must be solved for an infinite set of values of n. This problem can be solved by many different algorithms (some have simple solutions but take a long time to solve, while others are more complicated but take less time).

另外一种不可解的 “ 大量问题 ” 在形式化理论上称为所谓的判定问题 。希尔伯特第十问题涉及所谓的 “ 判定问题 ” ，即此问题包含个数无限的个体问题，每个都要求明确的回答：是或否。判定性问题的本质是要求寻找一个方法，使它对于所有的个体子问题都有明确的答案。自丢番图提出著名的 “ 丢番图方程 ” 之后，很多通过数论方法得以解决，还有很多被证明是不可解的。不幸的是，解决不同种类的方程和不同的个体方程，需要发明不同的，具体的方法。在第十问题中，希尔伯特要求一种通用方法来判定所有丢番图方程的可解性。 Another kind of unsolvable "mass problems" are the so-called decision problems for formal theories. Hilbert's tenth problem relates to the so-called "decision problems", i.e. the problem consisting of an infinite number of individual problems, each requiring a definite answer: YES or NO. The essence of a decision problem is requirement to find a single method that will give an answer to any individual subproblem. Since Diophantus has formulated his famous "Diophantus equations", many of them have later been solved by the number-theorists, and many others have been proved to be unsolvable. Unfortunately to solve different classes of equations and many individual equations, it was necessary to invent different specific methods. In his Tenth problem, Hilbert asks for an universal method for determining the solvability of Diophantus' equations.

1936 年，图灵，波斯特和丘奇提出了第一个关于算法的形式化概念。显而易见，同时他们发现首个不可解的大量问题。此后不久即时 1950 年，马丁 ·  戴维斯   在他的博士论文（参阅http://cs.nyu.edu/cs/faculty/davism/）中向证明希尔伯特第十问题具有否定答案，即丢番图方程的不可解迈出了第一步。 In 1936 Turing, Post and Church, introduced the first formalized concepts of algorithm. Obviously, they also discovered the first unsolvable mass problems. Soon after this, in his Ph.D. theses of 1950 Martin Davis (see http://cs.nyu.edu/cs/faculty/davism/) made the first step to prove that Hilbert's Tenth problem is unsolvable.

朱莉 - 罗宾逊  Julia Robinson

美国数学家朱莉 - 罗宾逊的名字不能与希尔伯特第十问题分开。让我们回顾朱莉 - 罗宾逊的科学生涯传记。罗宾逊生于 1919 年 12 月 8 日 ， 1985 年 7 月 30 日 卒于美国。圣地亚哥高中毕业后，她进入圣地亚哥州学院，后来转学到加州的加利福尼亚大学。罗宾逊 1984 年获得博士学位，并同年开始研究希伯特第十问题。她和马丁 · 戴维斯 ，希拉里 · 普特南一起提出的基础性研究成果，为后来解决希尔伯特第十问题打下基础。在 1970 年马蒂亚塞维奇解决此问题后，罗宾逊和马蒂亚塞维奇仍然为此问题做出重要的研究工作。 The name of the American mathematician Julia Robinson cannot be separated from Hilbert's tenth problem. Let us consider scientific biography of Julia Robinson. She was born on December 8, 1919 and died on July 30, 1985 in USA. After graduating from San Diego High School she entered San Diego State College. Later she transferred to the University of California at Berkley. Robinson was awarded a doctorate in 1948 and in the same year started to work on Hilbert's tenth problem. Along with Martin Davis and Hilary Putman she produced a fundamental result, which contributed to the solution of Hilbert's tenth problem. She also did important work on that problem with Matiyasevich after he gave the solution in 1970.

朱莉 - 逻宾逊（ 1919-1985 ） 

朱莉 - 罗宾逊一生获得许多荣誉。她 1975 年入选国家科学院，成为第一位女院士； 1978 年成为美国数学协会的首位女官员， 1982 年成为该协会的首位女会长。 1982 年，她入选美国艺术和科学研究院。 1983 年她因在数学上的建树而荣获麦克阿瑟学者奖。 Julia Robinson received many honors. She was the first woman to be elected to the National Academy of Sciences in 1975, the first woman officer of the American Mathematical Society in 1978 and the first woman president of the Society in 1982. She was elected to the American Academy of Arts and Sciences on 1984. She was awarded a MacArthur Fellowship in 1983 in recognition of her contribution to mathematics.

马蒂亚塞维奇  Jury Matiyasevich

希尔伯特第十问题在 1970 年已被当时年青的俄国数学家马蒂亚塞维奇解决了。但马蒂亚塞维奇是何许人也？ 1947 年 3 月 2 日 ，马蒂亚塞维奇出生于苏联的列宁格勒。 1969 年他毕业于列宁格勒州大学的数学系和机械系，同时在斯捷克洛夫数学研究所列宁格勒分校继续攻读硕士学位。他自 1970 年开始工作于该研究所，目前担任数理逻辑实验室主任。 Hilbert's tenth problem had been solved by the young Russian mathematician Yuri Matijasevich in 1970. But who is Yury Matiyasevich? Yuri Matiyasevich was born on March 2, 1947 in Leningrad, the USSR. In 1969 he graduated from Department of Mathematics and Mechanics of Leningrad State University and continued his study as post-graduate student at the Steklov Institute of Mathematics, Leningrad Branch. Since 1970 he works in this institute, currently as the Head of the Laboratory of Mathematical Logic.

自 1970 年马蒂亚塞维奇完成证明希尔伯特第十问题具有否定答案中最后缺失的一环后，他的名字在全世界变得广为人知。 The name of Yuri Matiyasevich became known worldwide in 1970 when he completed the last missing step in the "negative solution" of Hilbert's tenth problem.

马蒂亚塞维奇是法国日德奥弗涅大学的荣誉博士（ 1966 年）和俄罗斯科学院的通迅员（ 1997 年）。在他那两篇著名的文章《希尔伯特第十问题：连接数论和计算机科学的桥梁》和《与朱莉 - 逻宾逊的合作之路》（http://logic.pdmi.ras.ru/~yumat/Julia/）里面谈到他的发现之史和他和朱莉 - 逻宾逊的合作之史。 Yuri Matiyasevich is Docteur Honoris Causa de Universite d'Auvergne, France (1966) and Correspondent Member of the Russian Academy of Sciences (1997). He stated a history of his discovery and a history of his collaboration with Julia Robinson in his remarkable articles "Hilbert's Tenth Problem: A two-way Bridge between Number Theory and Computer Science" and "My collaboration with Julia Robinson" (http://logic.pdmi.ras.ru/~yumat/Julia/).

据文章介绍， 1965 年当马蒂塞亚维奇还是列宁格勒州大学数学系和机械系二年级学生的时候，他就开始研究希尔伯特第十问题。那时候，他熟悉马丁 · 戴维斯 ,   希拉里 · 普特南和朱莉－逻宾逊撰写的文章。这篇文章和私下与朱莉 - 罗宾逊的交流极大地推动了他的研究工作。According to these articles, he began to study Hilbert's tenth problem in 1965 when he was a sophomore in the Department of Mathematics and Mechanics of Leningrad State University. At this time he familiarized himself with the article by Martin Davis, Hilary Putman and Julia Robinson on Hilbert's tenth problem. Matiyasevich's work was greatly influenced by this article and personal contact with Julia Robinson.

马蒂亚塞维奇（左边）和 Maxim Vsemirnov 一起（ 1997 年 11 月，俄罗斯圣彼得堡）

限于篇幅问题，本文不能包含所有马蒂亚塞维奇关于数学细节的分析，尽管这些分析使他解决了希尔伯特第十问题。但我很乐意设法列出关于使用斐波纳契数的一般思想。 The scope of this article does not allow us to include all mathematical details of Yuri Matiyasevich's analysis, which led him to the solution of Hilbert's tenth problem. We would like to try to outline some general ideas concerning to usage of the Fibonacci numbers.

我们还是看看马蒂亚塞维奇是如何说的吧： However, let us allow Yuri Matiyasevich speak for himself:

“   想法如下：一般计算科学表示信息的工具使用单词而非数字。然而，使用数字来表示单词的方法有多种。其中有一种很自然地与丢番图方程关联。即不难证明任何   2 X 2 矩阵  "The idea was as follows. A universal computer science tool for representing information uses words rather than numbers. However, there are many ways to represent words by numbers. One of such methods is naturally related to Diophantus equations. Namely, it is not difficult to show that every 2 X 2 matrix 

其中 mij 为非负整数，并且行列式值为 1 ，可以唯一地表示为下面两种矩阵之积  with the m's being non-negative integers and the determinant equal to 1 can be represented, in any unique way, as a product of matrices

可以证明任意个数的此类矩阵之积是一个矩阵，它的每个元素均为非负整数，并且它的行列式值为 1 。这意味着我们可以使用四元组 (m₁₁ , m₁₂ , m₂₁ , m₂₂ ) 唯一表示只含两个字母的字母表中的单词 ，如下：It is evident that any product of such matrices has non-negative integer elements and the determinant equals 1. This implies that we can uniquely represent a word in two-letter alphabet by the four-tuple (m₁₁, m₁₂, m₂₁, m₂₂) such that

显然数值 m₁₁ , m₁₂ , m₂₁ , m₂₂ 满足丢番图方程   the numbers evidently satisfy the Diofantine equation

m ₁₁ x m ₂₂ - m ₂₁ x m ₁₂ = 1.

依照这种使用矩阵表示单词的方法，单词间的串接运算对应矩阵的乘法运算，因此很容易将单词运算表示为丢番图方程系。这为把任意单词方程系转换成等价的丢番图方程开辟一种新方法。许多关于单词的判定问题已被证明为不可判定问题，因此很自然通过证明单词方程系的不可判定性来设法攀登希尔伯特第十问题。 ” Under this representation of words by matrices, the concatenation of words corresponds to matrix multiplication and thus can be easily expressed as a system of Diophantus equations. This opens a way to transform an arbitrary system of word equations into equivalent Diophantus equations. Many decision problems about words had been shown undecidable, so it was quite natural to try to attack Hilbert's tenth problem by proving the undecidability of systems of word equations".

我们可以从下面得到结论：马蒂亚塞维奇的主要方法是通过证明单词方程系的不可判定性来演绎推导丢番图方程的不可判定性。 It can be concluded from the following that the main idea of Matiyasevich's approach is reducing a solution of the undecidability of Diophantus equations by proving the undecidability of systems of word equations!

下段我们将看到马蒂亚塞维奇是如何想到一种新方法即使用斐波纳契数来解决希尔伯特第十问题的。马蒂亚塞维奇写道： In the next passage we can see how Yuri Matiyasevich came up with the idea of using the Fibonacci numbers for solving the Hilbert's tenth problem. Matiyasevich writes:

下一步是考虑一类带有谓词的更广的单词方程。由于最终目标终始是希尔伯特第十问题，所以我仅考虑那些可以表示（或经过一定编码后可以表示）为丢番图方程的谓词。依照这一方法，我想到那些关于单词和长度的方程，可以通过使用著名斐波纳契数来简化。众所周知，任何自然均可唯一地表示为任意不同的和不连续的斐波纳契数之和。因此，我们可以把自然数看成为只有两个字符 {0 ,1} 的字母表中的单词，其中有一限制就是字母表中的单词不能有两个相连的 1^{[ 注 ]} 。我可以证明，按照此方法使用字数表示单词，那么单词的串接运算，以及单词间的长度关系式均可表示为丢番图方程 ” 。   "My next attempt was to consider a broader class of word equations with additional predicates. Since the ultimate goal was always Hilbert's tenth problem, I could consider only such predicates, which (under suitable coding) would be represented by Diophantus equations. In this way I came to what I have called equations in words and length. Reduction of such equations was based on celebrated Fibonacci numbers. It is well known that every natural number can be represented, in an almost unique way, as the sum of different Fibonacci numbers, none of which are consecutive (so called Zeckendorf representation). Thus we can look at natural numbers as words in two-letter alphabet {0, 1} with additional constraint that there cannot be two consecutive 1's. I managed to show that under this representation of words by numbers both the concatenation of words and the equality of the length of two words can be expressed by Diophantus equations".

[ 译者注 ] 任何自然数均表示为任意不同的不连续的斐波纳契数之和，例如 30 可以表示为 30=21 + 8 + 1=21 x 1¹ +13 x 1⁰ +8 x 1¹ +5 x 1⁰ +3 x 1⁰ +2 x 1⁰ +1 x 1¹ 。因此数字 30 对应的单词是 “1010001” 。由于表达中不存在连续的斐波纳契数，故对应的单中不存在连续的两个 “1” 。  

齐肯多夫表述法  Zeckendorf representation

对于比利时博士爱德华 . 齐肯多夫 (1901-1983) 来说，他简直不敢相像，他在数学上的造诣会有如此大的影响。他的数学成果之一就是被用来解决了希尔伯特第十问题，那就是著名的 “ 齐肯多夫和式 ” 问题，即齐肯多夫表述法。 1939 年曾他发表论文证明定理：任意正整数均可唯一地表示为非连续的斐波纳契数之和。 Hardly the Belgian doctor Eduardo Zeckendorf (1901-1983) could guess, that his infatuation with mathematics will appear so severe, that one of his mathematical outcomes will be used at the solution of Hilbert's tenth problem. The question is one of the famous "Zeckendorf's sums" or Zeckendorf's representation". In 1939 he published the article, in which he proved the theorem that every positive integer can be represented uniquely as the sum of non-consecutive Fibonacci numbers.

让我们以一个简单来的例子来说明此定理。假定要求使用斐波纳契编码来表示整数 30 。首先选择斐波纳契数： 1 ， 1 ， 2 ， 3 ， 5 ， 8 ， 13 ， 21 作为位权。然后列出整数 30 可表示为这些斐波纳契数之和的等式： 30 = 21 + 8 + 1 = 21 + 5 + 3 + 1 = 13 + 8 + 5 + 3 + 1 = 13 + 8 + 5 + 2 + 1 + 1 。最后在这些等式中唯一选取 30 = 21 + 8 + 1 ，因为只有该等式不存在连续的斐波纳契数。 Let us explain this theorem on a simple example. Suppose it is required to present the number 30 in the Fibonacci code. Let us choose the following Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21 as digit weights for such representation. Then there are some ways of the number 30 representation using sums of the Fibonacci numbers: 30 = 21 + 8 + 1 = 21 + 5 + 3 + 1 = 13 + 8 + 5 + 3 + 1 = 13 + 8 + 5 + 2 + 1 + 1. But among them it is possible to select one and only one representation 30 = 21 + 8 + 1, in which no consecutive Fibonacci numbers are being used.

请注意，上述的 “ 齐肯多夫表述法 ” 又称为 “ 最小形式 ” 。在上面本文系列中提到，最小形式是 “ 斐波纳契算术 ” 的基石。提得一提的是，许多主题为 “ 齐肯多夫和式 ” 的文章发表在《斐波纳契季刊》。 Note, that the mentioned above "Zeckendorf representation" is called also the "minimal form". The minimal form is a basis of "Fibonacci Arithmetic" considered above in our Museum. It should be noted, that many articles on the subject of "Zeckendorf's sums" were published in "The Fibonacci Quarterly".

引人注目的朱莉－逻宾逊 Striking Julia Robinson

然而，使用斐波纳契数和 “ 齐肯多夫表述法 ” 这一想法仅是解决希尔伯特第十问题中重要的一步。正如马蒂亚塞维奇回忆道 “ 无论如何，我还不能证明单词方程和单词长度方程的不可判定性（并且这仍然是一个开放问题） ” 。时下急需一种新的想法将此问题推向新的台阶，朱莉 - 逻宾逊顺应数学发展潮流提出了这样的方法。让我们看看马蒂亚塞维奇是这样说的： However the idea of usage of Fibonacci numbers and "Zeckendorf representation" was only some relevant step in the solution of Hilbert's tenth problem. As Matijasevich recalls "however, I was unable to show the undecidability of equations in words and length (and this problem remains an open problem)". There was a necessity in a new idea, which could advance a solution of the problem. And Julia Robinson became the author of such idea. However let us give a word to Yuri Matiyasevich:

“1969 年秋天，一位同事跟我说： “ 快去图书馆，朱莉 - 逻宾逊在最近一期的美国数学社会学报上发表了新的论文！ ” 但我早已把希尔伯特第十问题搁置一边了，对自己说 “ 朱莉 - 逻宾逊在此问题上取得新的进展，这很好，但我不能再花时间在此了 ” ，故我没有去图书馆。  "One day in the autumn of 1969 some of my colleagues told me: "Rush to the library. In the recent issue of the Proceedings of the American Mathematical Society there is a new paper by Julia Robinson!" But I was firm in putting Hilbert's tenth problem aside. I told myself: "It's nice that Julia Robinson goes on with the problem, but I cannot waste my time on it any longer". So I did not rush to the library.

数学天堂的某处必定有位上帝或女神，冥冥中注定我要读到朱莉 - 逻宾逊的新论文。由于我早期在此领域上发表的论文，业已成为该领域的专家，因此《数学参考学报》以苏联数学评论员的身份向我邮寄了论文，以予评论。这样我出奇不意地阅读了朱莉 - 逻宾逊的文章，并且 12 月我们在 LOMI 举行的逻辑研讨会上我介绍了她的论文。   Somewhere in the Mathematical Heavens there must have been a God or Goddess who would let me fail to read Julia Robinson's new paper. Because of my early publications on the subject, I was considered as a specialist on it and so the paper was sent to me to review for "Mathematics Reference Journal", the Soviet counterpart of "Mathematical Reviews". Thus I was forced to read Julia Robinson's paper, and on December 11, I presented it to our logic seminar at LOMI".

希尔伯特第十问题再次吸引住我，我立即看到朱莉 - 逻宾逊提出一种新奇的方法。这种方法使用了一种特殊的佩尔方程   Hilbert's tenth problem captured me again. I saw at once that Julia Robinson had a fresh and wonderful idea. It was connected with the special form of Pell's equation

x ² -   (a ² -1) y ² = 1.                                 (1)

以递增的顺序列出方程的解 {c 0 , f 0 }, {c 1 , f 1 }, ..., {c n , f n }, ..  ，则满足递归关系   Solutions {c₀, f₀}, {c₁, f₁}, ..., {c_n, f_n}, ... of this equation listed in the order of growth satisfy the recurrent relations

c n+1 = 2a     c n     -     c n-1 ,                    (2)  

f n+1 = 2a     f n   -     f n-1                       (3)

很容易证得，对于任意的 m ，数列 ntilde_0 , ntilde_1 , ...  和数列 f0 , f1 , ...  都是关于模 m 的纯周期数列，因此它们的线性组合也是关于模 m 的纯周期数列。通过归纳，从而得到数列 It is easy to see that for any m the sequences ntilde_₀, ntilde_₁, ..., f₀, f₁, ... are purely periodic modulo m and hence so are their linear combinations. Further, it is easy to check by induction that the period of the sequence

f 0 , f 1 , ..., f n , ...     (mod    a -1)               (4)

的周期性是

0,     1,      2,     ...,      a-2,

而数列

c0 - (a -2)  f 0 ,    c1 - (a - 2)  f1 ,     ...,  cn - (a -2) fn ,     (mod    4a-5)        (5)

的周期性始于

2⁰ , 2¹ , 2² , ... .

朱莉 - 逻宾逊的主要新思想是引入一个条件 G(a) 来同步两个数列， G(a) 可以保证数列（ 4 ）的周期长度是数列（ 5 ）的倍数。 The main new idea of Julia Robinson was to synchronize the two sequences by imposing a condition G(a) which would guarantee that the length of the period of (4) is a multiple of the length of period of (5)".  

我们不打算深入分析朱莉 - 逻宾逊完美的数学论证，因为我们坚信她在数学上取得杰出的成果。我们回到马蒂亚塞维奇的文章上来，细细体味朱莉 - 逻宾逊的研究成果是如何影响他的数学生涯。 We would not go deep into very nice mathematical reasoning's by Julia Robinson and we will take on faith her outstanding mathematical result and again we address to Matiyasevich's articles to evaluate how its result influenced on his mathematical discovery.

沃罗比约夫定理 Vorobev's Theorem

马蒂亚塞维奇写道： Yuri Matiyasevich wrote:

“ 经过先前的研究工作，我认识到斐波纳契数在解决希尔伯特第十问题中的重要性。这正是我为什么在 1969 年夏季怀着极大兴趣去阅读那本关于斐波纳契数的书，这是一本由沃罗比约夫在列宁格勒所写第三个修订版。令人难以置信的是，由斐波纳契在 13 世纪引进的斐波纳契数，竟然有人能在 20 世纪在兔子繁殖中，独具慧眼，发现了斐波纳契数中新的东西。然而，这本新版书不仅包含了传统的斐波纳契数知识，还囊括了作者原创性的研究成果。事实上，沃罗比约夫业已在四分之一世纪前取得了这些成果，只是此前他一直没有对外公布。他的研究成果马上吸引了我，但我仍然未能马上使用它来构造一种指数增长关系的丢番图表达式。   "Due my previous work, I realized the importance of Fibonacci numbers for Hilbert's tenth problem. That is why during summer of 1969 I was reading with great interest the third augmented edition of a popular book on Fibonacci numbers written by N.N. Vorob'ev from Leningrad. It seems incredible that in the 20th century one can still find something new about the numbers introduced by Fibonacci in the 13th century in connection with multiplying rabbits. However, the new edition of the book contained, besides traditional stuff, some original results of the author. In fact, Vorob'ev had obtained them a quarter of a century earlier but he never published anything before. His results attracted my attention at once but I was not able to use them immediately for constructing a Diophantus representation of a relation of exponential growth".

马蒂塞亚维奇这样评价沃罗比约夫和朱莉 - 逻宾逊对他在解决希尔伯特第十问题上的影响： Evaluating Vorobev's and Robinson's influence on his solution of Hilbert's tenth problem Matiyasevich wrote:

“ 我没有思考丢番图方程的那段时间，沃罗比约夫定理和朱莉 - 逻宾逊的新方法带领我步入希尔伯特第十问题的负解领域。 1970 年 1 月，我在我协会里首次作了关于指数增长丢番图关系的演讲。   "The period when I was not thinking about Diophantus equations, Vorobev's theorem and new ideas of Julia Robinson led me to negative solution of Hilbert's tenth problem. On January, 1970 I gave at my institute the first talk on a Diophantus relation of exponential growth ...

令人惊讶的是，为了构造这种指数增长关系的丢番图表示，我需要证明一个更新的，关于斐波纳契数的纯数论结果，第 k   个斐波纳契数可被第   l   个斐波纳契数的平方整除，当且仅当   k   自身可被第   l   个斐波纳契数整除   。这个性质本身不难证明，但令人不敢相信的是，自斐波纳契时代起竟无人从理认上，甚至从经验上发现这一美丽的事实。   Surprisingly, in order to construct a Diophantus representation for this relation I needed to proof a yet new purely number-theoretical result about Fibonacci numbers, that k-th Fibonacci number is divisible by the square of the l-th Fibonacci number if and only if k itself is divisible by the l-th Fibonacci number. This property is not difficult to prove; what is striking is that this beautiful fact has not been discovered, even empirically, since Fibonacci times".

并且马蒂亚塞维奇更进一步地评价沃罗比约夫和朱莉 - 逻宾逊对他解决希尔伯特第十问题所起的作用如下：And further Yuri Matiyasevich evaluated a role of Nikolay Vorobev and Julia Robinson in his solution of Hilbert's tenth problem as the following:  

“ 我原来的证明 …… 是基于苏联数学家沃罗比约夫在 1942 年证明的定理，他只把定理发表在他那本流行书的第三版修订版上。   "My original proof ...was based on a theorem proved by the Soviet mathematician Nikolay Vorob'ev in 1942 but published only in the third augmented edition of his popular book.

…… 读完朱莉 - 逻宾逊的论文后，我马上明白沃罗比约夫定理非常有用。 1970 年朱莉 - 逻宾逊从我这收到此书的副本，此前她一直没有读过沃罗比约夫那本书的第三版。如果沃罗比约夫把他的定理收录在此书的第一版里，谁能知道有什么事情发生呢？也许希尔伯特第十问题就提前十年解决了！ ” ... After I read Julia Robinson's paper I immediately saw that Vorob'ev's theorem could be very useful. Julia Robinson did not see the third edition of Vorob'v's book until she received a copy from me in 1970. Who can tell what would have happened if Vorob'ev had included his theorem in the first edition of his book? Perhaps Hilbert's tenth problem would have been "unsolved" a decade earlier!"

朱莉 - 逻宾逊与马蒂亚塞维奇  Julia Robinson and Yuri Matiyasevich

马蒂亚塞维奇如下描述朱莉 - 逻宾逊对他研究工作的影响：About influence of Julia Robinson works on his research Yuri Matiyasevich wrote the following:  

我试图用一个相当诗意的俄语单词 “íàâåÿòü” 来表明朱莉 - 逻宾逊论文对我研究工作的影响。尽管在英文里没有直接与之对应的单词，但后来翻译学者把它翻译成简明的 “ 暗示 ” 一词。 "I tried to convey the impact of Julia Robinson's paper on my work by a rather poetic Russian word "íàâåÿòü", which seems to have no direct counterpart in English, and the later English translator used plain "suggested".  

朱莉－逻宾逊和马蒂亚塞维奇，两位同时代杰出的数学家，在第四届国际逻辑、方法学和科学哲学大会上首次会面。这次会面是他们友谊的开始，也奠定他们高创造性的合作关系。 1973 年，卓越的苏联数学家安德雷 · 安德耶维齐 · 马尔可夫庆祝他的七十大寿。为了纪念他的七十大寿，苏联科学研究院计算中心的同事决定出版论文集，并向马蒂亚塞维奇邀稿。马蒂亚塞维奇主动和朱莉 - 逻宾逊合作论文并，并征得编辑同意提交。他们第二次合作的论文发表在《算术学报》上。 1974 年，美国数学界在伊利诺斯州迪卡尔布组织关于 “ 源于希尔伯特问题的数学发展 ” 的座谈会。马蒂亚塞维奇被大会邀请发表关于希尔伯特第十问题的讲话，但由于没有得到前苏联的批准，只能由朱莉 - 逻宾逊作为此问题的发言者。 The first meeting of Julia Robinson and Yuri Matiyasevich, two outstanding contemporary mathematicians, took place in Bucharest during the IV International Congress on Logic, Methodology and Philosophy of Science. Their first meeting became a beginning of their friendship, which found itself highly productive in creative relation. In 1973, the prominent Soviet mathematician A.A. Markov celebrated his seventieth birthday. His colleagues from the Computing Center of the Academy of Science of the USSR decided to publish a collection of papers in his honor. Yuri Matiyasevich was invited to contribute to the collection. According to his initiative the first joint paper with Julia Robinson was submitted to the collection and the editors agreed with such proposal. Their second joint paper was published on Acta Arithmetica. In 1974, the American Mathematical Society organized a symposium on "Mathematical Developments Arising From Hilbert's Problems" at DeKalb, Illinois. Yuri Matiyasevich was invited to speak about Hilbert's tenth problem but his participation in the meeting did not get the necessary approval in the former USSR, so Julia Robinson became the speaker on the problem.

下面照片于 1982 年年底拍于卡尔加里，当时马蒂亚塞维奇正在加拿大参加为期三个月的由马尔可夫数学研究所和金斯敦的女皇大学共同举办的科学交流项目。当时尽管朱莉 - 逻宾逊担任美国数学界主席一职非常忙碌，但她仍然从百忙中抽空到卡尔加里参加数学界会议。与此同时，马丁 ·  戴维斯   也到卡尔加里逗留几天。The photo below was taken in Calgary at the end of 1982 when Yuri Matiyasevich spent three months in Canada as participant of a scientific exchange program between the Steklov Institute of Mathematics and Queen's University at Kingston. Ontario. At that time Julia Robinson was very much occupied with her new duties as President of the American Mathematical Society but she was able to visit Calgary on her way to a meeting of the Society. Martin Davis also came to Calgary for a few days.

自左至右：马丁 ·  戴维斯   ，朱莉 - 逻宾孙和马蒂亚塞维奇 卡尔加里， 1982

引用朱莉 - 逻宾逊给马蒂亚塞维奇信中的内容，我们乐意从出类拔萃的数学发现史层面上来总结全文． We would like to conclude this article on a history of the outstanding mathematical discovery with quote from Julia Robinson's letter to Yuri Matiyasevich:

“ 事实上，我们一起工作（即使相隔千里）所取得的进步远胜于我们独自研究所能取得的进步，为此我深感高兴 ” 。 "Actually I am very pleased that working together (thousands miles apart) we are obviously making more progress than either one of us could alone".

References:

[1] https://zh.wikipedia.org/wiki/希爾伯特第十問題:  https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem:

第十問題的解決是眾人集體的智慧結晶。其中美國數學家马丁·戴维斯（英语：Martin Davis）（Martin Davis）、希拉里·普特南（Hilary Putnam）和朱莉娅·罗宾逊（英语：Julia Robinson）（Julia Robinson）做出了突出的貢獻。而最終的結果，是由俄國數學家尤里·马季亚谢维奇（Yuri Matiyasevich）於1970年所完成的。

[2] https://logic.pdmi.ras.ru/~yumat/talks/index.php

[3] https://scholar.google.com.au/citations?user=WnOjCtEAAAAJ&hl=en&oi=ao