Saturday, October 23, 2010

悖論與Halting Problem

悖論是指某些奇特的推論。這些推論的假設和邏輯看似合理,但卻帶出明顯地不可接受的結論。(思方網) 
用邏輯的語言來說,悖論就是若假設命題A為真,經過一系列合理的推導,最終卻得到命題A為假的結論。

Halting Problem就是悖論的一個例子。Halting Problem是說是否可以寫一支程式,用來檢查任何一個程式是否會在有限的時間內結束。最後的結論是不可能存在這樣的一支程式,證明的方式正是利用悖論中的矛盾。

推導過程很簡單,首先假設這支程式已經存在,我們命名為H(M, w),M為任一支被檢查的程式,w為M的輸入參數。為了方便說明,我把H(M, w)表示成為虛擬碼。

Function H(M, w)
{
  if M(w) halts
    return true
  else
    return false
}

現在有趣的來了。如果H(M, w)真的存在,我們當然可以"Reuse"他去寫其他的程式。例如說,我可以寫一個P(K),虛擬碼如下:

Function P(K)
{
  if H(K, K) == true
    loop
  else
    return
}

這個P(K)是一個有可能會陷入無窮迴圈的程式。
然後,讓我們來考慮把P當做P(K)的參數,也就是P(P)事情會怎麼發展。

Case I: 如果P(P)會進入無窮迴圈,那H(P, P)就會傳回false,然後P(P)就會立刻結束(return)。

Case II: 如果P(P)會立刻結束,那H(P, P)就會回傳true,然後P(P)就會進入無窮迴圈。

嘿嘿,無論是哪一種Case,得出來的結論都自相矛盾。
因此,H(M, w)存在的命題必為假。也就是說,H(M, w)是不可能存在。


* * * * * * * *

這個證明的歷史可以追朔到Alan Turning在1937年發表的論文:"On Computable Numbers With an Application to the Entscheidungsproblem"。原始論文是用Universal Turing Machine來證明。

2 comments:

Unknown said...

向顏葛格好厲害喔 >///<

Unknown said...

這不是離散數學必教的嗎...