可運算性

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

可運算性英文computability),又叫做可計算性,係指一個問題有冇可能可以用運算嘅方法解決-如果一個問題係可以用電腦解決嘅,噉呢個問題就係可運算嘅,否則呢個問題就係不可運算嘅。

概論[編輯]

睇埋:運算理論

舉個例說明,好似係好出名嘅停機問題(halting problem)噉:首先,電腦程式可以分做兩大種[1]

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

根據英國數學家亞倫圖靈證明,呢個世界冇可能有電腦能夠攞一個程式嘅碼做輸入,再俾出正確嘅「呢段碼會唔會停機」輸出(停機問題)。圖靈用嘅係反證法(proof by contradiction),證明如果呢個世界上有個程式能夠做到噉嘅工作,就會發生一啲冇可能嘅事。呢個證明大致上係噉嘅[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.