嗯 偶爾有些人會透過halting problem搜尋到我的blog
(因為以前求學的一篇報告有引用到halting problem)
我想有些人應該是要找halting problem的證明說明
所以po了這篇 把以前整理的證明供人參考用


在證明之前 最近也因為halting problem看了一些「悖論」
所謂的悖論 簡單的說 當假定某A為真時 經過正確的證明後 卻得到某A為假的結論
halting problem就是一種悖論
它是說 我們無法找出一個Turing machine來證明另一個Turing machine的結果是對的
假設有這樣的機器存在 經過證明後 會得到這樣機器並不存在
好 相信沒學過的人 聽到這邊還是完全不知道我在說什麼
所以舉兩個在wiki上面看到的好玩悖論與大家分享


一個是時光理論中很有名的「祖父悖論」
假設有時光機存在 小明坐時光機回到過去殺了他的祖父
這樣小明還會存在嗎? 如果不存在 小明又怎麼回到過去殺他祖父
(平行宇宙理論可以解決此問題 不過 那只是一種猜測)


另外一個好玩的悖論是「全能悖論」
假設有上帝的存在 且上帝是全能的
那上帝能創造一個自己也舉不起來的石頭嗎?
若不能創造這種石頭 那上帝就不是全能的
若能 那上帝舉不起來該石頭 一樣代表上帝不是全能的
因此 就算有上帝 他也不可能是全能的
所以 禱告時 「萬」能的神會比「全」能的神來得貼切些 XD

延伸閱讀:「結束了沒?」

亂扯了一通 最後po上halting problem的證明
-----------------------------------------------------
對於 input M,w 其中 M 是一個 Turing machine, w 是 Turing machine M 的 input
使得 H(M, w) : if M(w) = halt return accept
else return reject
也就是如果 M 對input w 會停,則 H 回答 accept; M 對 w 不會停 H 回答 reject
而halting problem 就是說不可能造出一個 Turing machine H


假設可以造的出 H 來,我們可以造出另一個 Turing machine D
Turing machine D 的製造方式如下:
1.另外製造一 H',H'的功能是從原先的 H 中增加一個新的transition fubnction如下:
「當一個輸入字串在H中是accept時,接下來會無限期地在tape上往右移動」
所以當 H 是accept時(也就是 M 會halt時),則 H' 會loop。
反之則 H' 會halt。
2.接下來將一個copy機器與 H' 合併成 D 。
D機器的輸入是編碼過的機器M,也就是課本上的R(M)
copy機器將R(M)複製的用意"可能"是把後面那個視為輸入字串。


D(M') = if H(M, M) = accept then loop
else return halt
Turing machine D 的功能是,如果 H(M, M) 是 accept, 則 D 會回答 loop
H(M, M) 是reject 則 D 會回答 halt


那我們就問 D(D) 會發生什麼情形?
假如 D(D) 回答 halt
根據上面 D 的定義 D(D) 回答 halt 是因為 H(D, D) 回答 reject
可是根據 H 的定義 H(D, D) 回答 reject 就表示 D(D) loop(就是不會halt) 矛盾


假如 D(D) 不會停
根據 D 的定義 D(D) 不會停是因為 H(D, D) 回答 accept
可是根據 H 的定義 H(D, D) 回答 accept 就表示 D(D) 會halt 矛盾
前面的推論之所以會導致矛盾的結果就是因為我們不可能造出 Turing machine H 來

創作者介紹

雁渡寒潭

wuyen 發表在 痞客邦 PIXNET 留言(1) 人氣()


留言列表 (1)

發表留言
  • N.C
  • 全能悖論還滿瞎的,根本是把神人格化了。