命題 #
前陣子才認識 Busy Beaver 問題：所有的 N 狀態圖靈機中，最慢停機者要花幾步（輸入為空白紙帶）？
此數 BB(N) 不可決策。因為它可以解決停機問題
- 給我一臺 N 狀態圖靈機和空紙帶，我可以模擬 BB(N) 步，來檢查會不會停機。
- 空紙帶停機問題有解。
- 給我一臺 M 狀態圖靈機和內容長度為 l 的紙帶，我可以造下述圖靈機，吃空紙帶模擬其停機與否。
- 2l+M 狀態的圖靈機，前 2l 個狀態會把給的內容寫到空紙帶上，再移動回起點，其餘 M 狀態與原本相同。
- 停機問題有解
新聞 #
今年有人機證出 BB(5) = 47,176,870。
主要難點是要證明某些 5 狀態圖靈機不會停機。所以說「證出」而非「算出」。
心得 #
以上不可決策性證明是抄維基百科的。我看完問題描述時並沒有發現它不可決策。 總覺得我大學讀四年連這個直覺都沒有，好像有點廢。
Busy Beaver 的中文維基條目叫「忙碌的海狸」。可是 Beaver 會築水壩，應該是河狸才對呀！