可運算度

可運算度（粵拼：ho2 wan6 syun3 dou6；英文：computability），又叫做可計算度，係指一個問題有冇可能可以用運算嘅方法解決－如果一個問題係可以用電腦解決嘅，噉呢個問題就係可運算嘅，否則呢個問題就係不可運算嘅。

概論

舉個例說明，好似係好出名嘅停機問題（halting problem）噉：首先，電腦程式可以分做兩大種^[1]：

例：while (true) continue；呢種程式唔會停機－部電腦一行呢個程式就會一路行落去，永世唔會停。

例：print "Hello, world!"；呢種程式會停機－部電腦會逐行逐行碼行咗佢，最後停低。

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

[1] Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (58): 345–363.

[turing1937-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.

[1]

[2]

[3]