停機問題
解釋 編輯
首先，運算上嘅問題可以分做兩大種[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.
- ↑ 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.
- ↑ 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.