兰姆达运算与德国著名的数学家希尔伯特第十问题有关.
尔伯特第十问题是一个与解方程有关的问题.这类方程被称为整系数代数多项式方程.数学家们对这类方程的研究有着漫长的历史.
公元三世纪的时侯,古希腊数学家丢番图 (Diophantus,200?-284?) 发表了一部长篇巨著,叫做 《算术》.丢番图在这部著作中对整系数代数多项式方程进行了大量的研究,这些研究对代数与数论的发展有着先驱性的贡献.后人为了纪念他,就把整系数代数多项式方程称为丢番图方程.
对于丢番图方程,数学家们最感兴趣的一个问题就是研究它是否有整数解 (或自然数解).但对于
一般的丢番图方程来说,判断它是否有整数解却往往是一件极其困难的事情,那么有没有办法对一般的丢番图方程是否有整数解进行研究呢?或者具体地说,是否可以找到一种普遍的算法,可以用来判定一个任意的丢番图方程是否有整数解,从而一劳永逸地解决这类问题呢?这便是著名的希尔伯特第十问题.
希尔伯特第十问题要求寻找判定丢番图方程是否有解的算法.但究竟什么是算法呢?在当时却没有一个明确的定义.这是研究希尔伯特第十问题所遇到的第一个困难.这一困难使得希尔伯特第十问题在提出后整整三十年没有取得任何实质进展.
二十世纪三十年代初的时侯,普林斯顿大学的美国逻辑学家丘奇 (Alonzo Church,1903-1995) 也在积极从事逻辑及算法的研究,并且发展出了一种新的逻辑体系.他让自己的两位学生 - 克林 (Stephen Kleene,1909-1994) 与罗瑟 (John Rosser,1907-1989) 对这一体系做细致的研究.他的这两位学生都是第一流的好手,克林后来自己也成为了第一流的逻辑学家,他们的研究很快就有了结果,但这结果却大大出乎丘奇的意料.他们发现丘奇的那套体系竟然是自相矛盾的!自相矛盾的逻辑体系只能有一个命运,那就是被放弃.但幸运的是,丘奇的那套体系中有一个组成部分仍然是自洽的,因此可以保留下来,这一部分叫做兰姆达运算 (λ-calculus).
这种兰姆达运算可以用来定义函数,而所有用兰姆达运算定义的函数都是可以有效计算的.