蘭姆達(dá)運(yùn)算與德國著名的數(shù)學(xué)家希爾伯特第十問題有關(guān).
爾伯特第十問題是一個(gè)與解方程有關(guān)的問題.這類方程被稱為整系數(shù)代數(shù)多項(xiàng)式方程.數(shù)學(xué)家們對這類方程的研究有著漫長的歷史.
公元三世紀(jì)的時(shí)侯,古希臘數(shù)學(xué)家丟番圖 (Diophantus,200?-284?) 發(fā)表了一部長篇巨著,叫做 《算術(shù)》.丟番圖在這部著作中對整系數(shù)代數(shù)多項(xiàng)式方程進(jìn)行了大量的研究,這些研究對代數(shù)與數(shù)論的發(fā)展有著先驅(qū)性的貢獻(xiàn).后人為了紀(jì)念他,就把整系數(shù)代數(shù)多項(xiàng)式方程稱為丟番圖方程.
對于丟番圖方程,數(shù)學(xué)家們最感興趣的一個(gè)問題就是研究它是否有整數(shù)解 (或自然數(shù)解).但對于
一般的丟番圖方程來說,判斷它是否有整數(shù)解卻往往是一件極其困難的事情,那么有沒有辦法對一般的丟番圖方程是否有整數(shù)解進(jìn)行研究呢?或者具體地說,是否可以找到一種普遍的算法,可以用來判定一個(gè)任意的丟番圖方程是否有整數(shù)解,從而一勞永逸地解決這類問題呢?這便是著名的希爾伯特第十問題.
希爾伯特第十問題要求尋找判定丟番圖方程是否有解的算法.但究竟什么是算法呢?在當(dāng)時(shí)卻沒有一個(gè)明確的定義.這是研究希爾伯特第十問題所遇到的第一個(gè)困難.這一困難使得希爾伯特第十問題在提出后整整三十年沒有取得任何實(shí)質(zhì)進(jìn)展.
二十世紀(jì)三十年代初的時(shí)侯,普林斯頓大學(xué)的美國邏輯學(xué)家丘奇 (Alonzo Church,1903-1995) 也在積極從事邏輯及算法的研究,并且發(fā)展出了一種新的邏輯體系.他讓自己的兩位學(xué)生 - 克林 (Stephen Kleene,1909-1994) 與羅瑟 (John Rosser,1907-1989) 對這一體系做細(xì)致的研究.他的這兩位學(xué)生都是第一流的好手,克林后來自己也成為了第一流的邏輯學(xué)家,他們的研究很快就有了結(jié)果,但這結(jié)果卻大大出乎丘奇的意料.他們發(fā)現(xiàn)丘奇的那套體系竟然是自相矛盾的!自相矛盾的邏輯體系只能有一個(gè)命運(yùn),那就是被放棄.但幸運(yùn)的是,丘奇的那套體系中有一個(gè)組成部分仍然是自洽的,因此可以保留下來,這一部分叫做蘭姆達(dá)運(yùn)算 (λ-calculus).
這種蘭姆達(dá)運(yùn)算可以用來定義函數(shù),而所有用蘭姆達(dá)運(yùn)算定義的函數(shù)都是可以有效計(jì)算的.