Halting problem 停機問題有多難

記得第一次聽到 Halting problem 時候，沒有覺得他那麼難，至少感覺上來說。儘管最後大家用到高等微積分裡面的Cantor的對角化法。但感覺還是還好，就是對角化法的應用而已。

可是我們可以試想如果可以的話，到底能解決啥問題?
答案是，可能目前超難的幾個數學問題都能被解決!!!!!!
先來敘述
Halting problems: 是否存在一個Turing machine algorithm
可以決定另一個 turing machine + input 是否會halts or loops forever. (停止或是進入無限迴圈)

Turing 圖靈給的解答是 : 不存在!!!!

證明:
假定存在一個D, 給一個M(turing machine 和一個 input, x) 
D(<M,x>) = 如果M(x)無限迴圈 輸出0
如果 如果M(x)停止 輸出1.

proof:
假設存在這個D，那我製造一個L 機器 定義如下
L(<M,x>)=如果M(x)無限迴圈 輸出1; 如果M(x)停止 輸出0. 這是可以做到的，因為D存在，L存在。
現在問:
L(<L>) 是什麼?
注意 by definition:
L(<L, L>) 要問 L(L) 是否停止或是無限迴圈。
如果  L(L)=0; 表示L 吃掉自己 會停止，但L(L)= 反過來的 D(<L, L>)
表示D(<L, L>)=1. 定義 L(L) 會無限迴圈。矛盾!!!!!!!!!!
如果假設反過來，也會是對的。

所以D does not exist.

計算機複雜度中有個很有名的定理 也用到一樣的證明，叫做Time Hierarchy Theorem。對類似問題有興趣的小夥伴，可以看我自己做的英文youtube影片。訂閱一下很歡迎。

這是Halting problem的影片:

這是Time Hierarchy Theorem影片:

好，如果覺得這證明頗智障，我們可以反過來想: 如果我現在可以解停機問題。那會怎樣。

以下給出幾個examples

(1) 我寫下一個program，program 去找 第一個大於2的偶數不能寫成兩個質數的和，找到，就halts.
4=2+2, 6=3+3., 8=3+5, 10=3+7.............
這叫做Goldbach's conjecture

這問題是open problems in mathematics。如果你可以解決，那你一定得費爾茲獎，如果我知道他會halts. 那就表示是錯了，如果loops forever, 那就是對的。這告訴你Halting problem 很難。

(2)寫一個program 尋找 x^n+y^n=z^n (n>2) 的正整數解，找到就停止。

這個問題是費馬大定理。一樣很難，1994 andrew wiles prove it. 花了數學家四百年。

Fermat's Last Theorem 

找黎曼猜想的反例? 世界上有多少六維的calabi yau? 世界上是否有無限多個雙生質數(twin prime conjecture)

.....都可以視為是 Halting problems的 子問題。以上這些問題都是超難超難的數學問題。

希望這樣可以讓大家感受到

Halting problem 停機問題有多難。




一些變形:
有些問題是 halting problem的變形:
比方 是否存在一個演算法 判斷 一個code 跟一個input 是否可以print "hello world'?
這個問題看起來也很智障，但可以證明 他跟 halting problem 等價?

證明很簡單:
那定義Ｇ程式(x): 如果這個程式 加上 input(x) 可以print hello world 則 halts
otherwise halts.

所以 如果 halting problem 可以被解 則  G可以被解 可以判斷一程式 加上一個input 是否會print hello world.
這證明了  halting problem  > hello world

反過來說
對於任意程式和 input x
我定義 G={如果halts 則輸出hello world 反之 則不輸出}

這樣解hello world 就可以解halting problem

這證明了  halting problem  < hello world.

還有很多問題 都一樣困難 推薦一個 3n+1 問題 大家可以看看唷。
3n+1 problems -- Collatz conjecture python code



Go back to Main page Notes for Complexity theory