停機問題

係運算理論上嘅一個問題，指出呢個世界冇可能有電腦能夠攞一個程式嘅碼做輸入，再俾出正確嘅「呢段碼會唔會停機」輸出。

解釋 
首先，運算上嘅問題可以分做兩大種：

例：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() 就唔會進入永遠係噉行嘅狀態－又出現矛盾。因為噉，如果呢個世界有電腦曉攞一個程式嘅碼做輸入，再俾出正確嘅「呢段碼會唔會停機」輸出嘅話，就會出現一個邏輯上嘅矛盾，所以呢一個程式冇可能存在喺呢個世界上－即係話「攞一個程式嘅碼做輸入，再正確噉判斷個程式會唔會停機」係一個不可運算嘅問題。

運算理論
可運算性
異質字悖論

攷 

電腦科學