歷史傳說
一位法國數學家曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟裡，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸於盡。
不管這個傳說的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，並且始終保持上小下大的順序。這需要多少次移動呢?這裡需要遞歸的方法。假設有n片，移動次數是f(n).顯然f⑴=1,f⑵=3,f⑶=7，且f(k+1）=2*f(k)+1。此後不難證明f(n)=2^n-1。n=64時，
f（64）= 2^64-1=18446744073709551615
假如每秒鐘一次，共需多長時間呢？一個平年365天有 31536000 秒，閏年366天有31622400秒，平均每年31556952秒，計算一下，
18446744073709551615/31556952=584554049253.855年
這表明移完這些金片需要5845億年以上，而地球存在不過45億年，太陽系的預期壽命據說也就是數百億年。真的過了5845億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。
基本介紹
漢諾塔是由三根桿子A，B，C組成的。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿：每次只能移動一個圓盤；大盤不能疊在小盤上面。提示：可將圓盤臨時置於B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須尊循上述兩條規則。問：如何移？最少要移動多少次？漢諾塔是根據一個傳說形成的一個問題：
有三根桿子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿：
每次只能移動一個圓盤；
大盤不能疊在小盤上面。
提示：可將圓盤臨時置於B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須尊循上述兩條規則。
問：如何移？最少要移動多少次？
相似問題
和漢諾塔故事相似的，還有另外一個印度傳說：舍罕王打算獎賞西洋棋的發明人──宰相西薩·班·達依爾。國王問他想要什麼，他對國王說：“陛下，請您在這張棋盤的第1個小格里賞給我一粒麥子，在第2個小格里給2粒，第3個小格給4粒，以後每一小格都比前一小格加一倍。請您把這樣擺滿棋盤上所有64格的麥粒，都賞給您的僕人吧！”國王覺得這個要求太容易滿足了，就命令給他這些麥粒。當人們把一袋一袋的麥子搬來開始計數時，國王才發現：就是把全印度甚至全世界的麥粒全拿來，也滿足不了那位宰相的要求。
那么，宰相要求得到的麥粒到底有多少呢？總數為
1+2^1+2^2 + … +2^63
和移完漢諾塔的次數一樣。我們已經知道這個數字有多么大了。人們估計，全世界兩千年也難以生產這么多麥子！
心理學知識
美國心理學家、人工智慧專家西蒙(Herbert A.Simon，1916~2001)和紐厄爾（Alan Newell ，1927—1992）把心理學結合起來，開創了人工智慧的研究，並致力於人類思維的計算機模型。20世紀50年代，他們首先設計了計算機模擬下象棋的程式，這一工作在當時被認為是開創性的。西蒙和紐厄爾把出聲思考用於問題解決的研究，並提出了問題行為圖的概念。問題行為圖使人們直接地看到在問題解決過程中所進行的各種操作的序列。他們認為，認知系統是一種模組化的結構，他由許多模組組成，每個模組負責解決不同類型的問題，不同功能的模組相互結合，採用和解決簡單問題一樣的解題策略，就能解決複雜的問題。通過問題解決者（General problem solver，GPS）就是他們對河內塔問題解決的計算機模擬。
“通過問題解決者”是世界上第一個問題解決的人工智慧程式。如今，人工智慧以及取得了長足的進步，並在需要速度、大容量記憶和較長時間的智力活中動情景中充分體現出其價值，在某些任務中比人類做的更好。
