可運算度

可運算度，又叫做可計算度，係指一個問題有冇可能可以用運算嘅方法解決－如果一個問題係可以用電腦解決嘅，噉呢個問題就係可運算嘅，否則呢個問題就係不可運算嘅。

概論

舉個例說明，好似係好出名嘅停機問題噉：首先，電腦程式可以分做兩大種：
例：while (true) continue；呢種程式唔會停機－部電腦一行呢個程式就會一路行落去，永世唔會停。
例：print "Hello, world!"；呢種程式會停機－部電腦會逐行逐行碼行咗佢，最後停低。

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

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

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

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

運算理論
運算複雜度
我哋而家唔知，將來都唔會知

攷

運算理論