停機問題

出自維基百科,自由嘅百科全書
Jump to navigation Jump to search

停機問題halting problem)係運算理論上嘅一個問題,指出呢個世界冇可能有電腦能夠攞一個程式嘅碼做輸入,再俾出正確嘅「呢段碼會唔會停機」輸出。

解釋[編輯]

首先,運算上嘅問題可以分做兩大種[1]

例:while (true) continue;呢種問題唔會停機-部電腦一行呢個程式就會一路行落去,永世唔會停。
例:print "Hello, world!";呢種問題會停機-部電腦會逐行逐行碼行咗佢,最後停低。

英國數學家亞倫圖靈(Alan Turing)對停機問題做咗證明:圖靈用嘅係反證法,證明如果呢個世界上有個程式能夠做到噉嘅工作,就會發生一啲冇可能嘅事。呢個證明大致上係噉嘅[2]

想像有個程式,halts(f),如果 f 係一個會停機嘅子程序halts(f) 會出「真」(1),否則halts(f) 會出「假」(0),再想像以下呢個程序:

def g(): # 定義 g
    if halts(g): # 如果 halt(g) 係真...
        loop_forever() # 做永遠唔停嘅 loop

呢個程序會引致一個大矛盾:如果 g() 係會停機嘅,噉 halts(g) 會出「真」,於是 g() 就會進入永遠係噉行(loop_forever)嘅狀態-出現矛盾;而如果 g() 係唔會停機嘅,噉 halts(g) 會出「假」,於是 g() 就唔會進入永遠係噉行(loop_forever)嘅狀態-又出現矛盾。因為噉,如果呢個世界有電腦曉攞一個程式嘅碼做輸入,再俾出正確嘅「呢段碼會唔會停機」輸出嘅話,就會出現一個邏輯上嘅矛盾,所以呢一個程式冇可能存在喺呢個世界上-即係話「攞一個程式嘅碼做輸入,再正確噉判斷個程式會唔會停機」係一個不可運算嘅問題[2][3]

睇埋[編輯]

[編輯]

  1. Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (58): 345–363.
  2. 2.0 2.1 Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42 (1937), pp 230–265.
  3. Davis, Martin (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press.. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.