停機問題
停機問題（粵音：ting4 gei1 man6 tai4；英文：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]。
睇埋
[編輯]引咗
[編輯]- ↑ Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (58): 345–363.
- 1 2 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.
- ↑ Davis, Martin (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press. 圖靈篇論文係呢本書嘅第三篇，其他論文嘅作者包括 Gödel、Church、Rosser、Kleene 同 Post。