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

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

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

朱莉娅·罗宾逊传记

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

她的大部分职业生涯都在追求可计算性和“决策问题，在正式系统中用"是的或"没有，这取决于某些输入参数的值。她特别热衷的是希尔伯特第10个问题，她痴迷地解决它。问题是要确定是否有办法判断某个特定的丢片图方程(变量只能是整数的多项式方程)是否有整数解。越来越多的人相信，不可能有这样一种万能的方法，但要真正证明永远不可能有这样一种方法似乎很难。

整个20世纪50年代和60年代，罗宾逊和她的同事们马丁·戴维斯和希拉里·帕特南他坚持不懈地研究这个问题，最终提出了著名的罗宾逊假说，该假说认为，为了证明不存在这样的方法，所需要做的就是构造一个方程，其解是一组非常具体的数字，这个方程的解是一组指数增长的数字。

这个问题困扰了罗宾逊20多年，她承认自己非常渴望在死前看到这个问题的解决方案，无论谁能实现它。

不过，为了进一步研究，她需要这位年轻的俄罗斯数学家的帮助，尤里Matiyasevich．

马蒂亚塞维奇出生在列宁格勒(圣彼得堡)，并在那里接受教育，他已经是一个杰出的数学天才，并在数学方面获得了许多奖项。他转向希尔伯特作为列宁格勒国立大学博士论文的主题，他开始与罗宾逊通信，了解她的进展，并寻找前进的道路。

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

Matiyasevich-Stechkin质数目视筛

作为冷战高潮时期数学国际主义的一个令人心酸的例子，马蒂亚塞维奇坦率地承认了他对罗宾逊的工作的感激之情，两人继续在其他问题上合作，直到1984年罗宾逊去世。

Matiyasevich-Stechkin质数目视筛

在他的其他成就中，Matiyasevich和他的同事Boris Stechkin还开发了一种有趣的“视觉筛对于质数，有效地穿过了"所有的合数，只留下质数。他有一个以他命名的关于递归可枚举集的定理，以及一个与球面三角剖分的着色有关的多项式。

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

<<回到科恩