横幅

Julia Robinson和Yuri Matiyasevich:可计算理论和计算复杂性理论

茱莉亚·罗宾逊和尤里·马蒂亚塞维奇

朱莉娅·罗宾逊(1919-1985)和尤里·马蒂亚塞维奇(1947-)

在一个几乎完全由男性主导的领域,茱莉亚•罗宾逊是少数对数学产生重大影响的女性之一吗?还有其他值得提及的女性吗索菲娅·杰曼和索菲亚·科瓦列夫斯卡娅在19世纪,而且艾丽西亚的以及20世纪的艾米·诺特,她成为了第一位当选为美国数学学会主席的女性。

茱莉亚·罗宾逊传记

在亚利桑那州的沙漠里长大在美国,鲁滨逊是个害羞多病的孩子,但从小就对数字表现出天生的热爱和熟练。她克服了许多障碍,努力争取继续学习数学,但她坚持了下来,在伯克利获得了博士学位,嫁给了一位数学家,她在伯克利的教授拉斐尔·罗宾逊。

她的大部分职业生涯都在追求可计算性和“决策问题,在正式系统中用“是的”或“没有的答案,这取决于某些输入参数的值。她的特别爱好是希尔伯特这是她的第10个问题,她痴迷地钻研着。问题是要确定是否有任何方法可以告诉任何特定的丢番图方程(一个变量只能是整数的多项式方程)是否有整数解。越来越多的人相信,这种普遍的方法是不可能存在的,但实际上证明这种方法永远不可能存在似乎非常困难。

在整个20世纪50年代和60年代,罗宾逊和她的同事们马丁·戴维斯和希拉里·帕特南他坚持不懈地研究这个问题,最终发展出了后来被称为“罗宾逊假说”的理论。该理论认为,为了证明不存在这样的方法,只需要构造一个方程,这个方程的解是一组非常特殊的数字,并且呈指数增长。

这个问题困扰了鲁滨逊20多年,她承认她非常想在死前看到这个问题的解决办法,不管是谁能做到。

然而,为了进一步发展,她需要这位年轻的俄罗斯数学家的帮助,尤里Matiyasevich

Matiyasevich出生并在列宁格勒(圣彼得堡)接受教育,他已经是一个杰出的数学天才,并在数学方面获得了无数奖项。他转向希尔伯特他在列宁格勒州立大学的博士论文中以鲁滨逊的第10个问题为主题,并开始与鲁滨逊通信,了解她的进展,并寻求一条前进的道路。

20世纪60年代末,马蒂亚塞维奇在研究这个问题之后,终于在1970年发现了拼图的最后一块缺失的碎片,当时他只有22岁。他看到了如何利用核心方程来捕捉著名的斐波那契数列希尔伯特他的第10个问题,因此,在罗宾逊早期工作的基础上,它最终证明,实际上不可能设计出一个过程,通过有限个数的运算来确定丢番图方程是否在有理整数中可解。

Matiyasevich-Stechkin质数视觉筛

Matiyasevich-Stechkin质数视觉筛

这是一个尖锐的例子,说明了在冷战高峰时期数学的国际主义。马蒂亚塞维奇坦率地承认罗宾逊的工作对他有帮助,两人继续在其他问题上合作,直到罗宾逊于1984年去世。

Matiyasevich-Stechkin质数视觉筛

在他的其他成就中,Matiyasevich和他的同事Boris Stechkin还发展了一个有趣的“视觉筛"对于质数而言"穿过了“所有的合数,只剩下质数。他有一个以他的名字命名的递归枚举集定理,以及一个与球体三角化着色有关的多项式。

他是俄罗斯科学院斯特克洛夫数学研究所圣彼得堡部数理逻辑实验室的负责人,也是几个数学学会和理事会的成员。


<<回到科恩

Baidu