Turing was Wrong?

剛在做GP的slide，突然想到一句簡單的介紹詞，

"從Turing發明電腦以來，人們就一直想知道二進位電腦，它的運算能力極限是什麼，"

但後面卻接不下去，因為我不確定GP是否有這麼大的能耐...

於是Google大神打下key word "Turing" "Genetic Programming"，

結果居然被我找到這個.......

http://tinyurl.com/ng37u

標題聳動到不行....2006.5.8
Turing was wrong: the halting problem may be decidable after all!

Selecting programs at random from the space of Turing-complete programs ... all ?

we show that almost all of them stop.

Therefore, the answer of the Halting problem is "no", with probability 1.

學正規和離散時，每次談到Turing machine的運算極限時，

一定會直覺想到Halting Problem...
(用對角線性質，或歸謬證法證明)

但這兩個傢伙想用GP來挑戰電腦極限了，

當電腦有能力超越Halting promblem時，

我覺得離"I Robot"的幻想世界，

又向前跨進一大步...