歡迎關(guān)注我的專欄( つ??ω??)つ【人工智能通識】
繁忙的海貍是個圖靈機游戲戴差，這一篇我們就認真的來看看這個可愛的小動物顶籽。
停機問題Halting Problem
之前我們介紹過基本的圖靈機春叫，讀寫頭Head可以不停地對紙帶上的數(shù)字（0或1）進行讀取，然后再跟進自身狀態(tài)State和讀取到的數(shù)字來決定下一步動作慈缔，以及下一步狀態(tài)切換减途。
但是圖靈機有一個問題，那就是它根據(jù)設(shè)定好的規(guī)則運行舒萎，并不一定能夠最終自動停下來程储，不停下來就代表計算沒有結(jié)束，沒結(jié)束就代表得不到結(jié)果。
一直運行卻永遠得不到結(jié)果的圖靈機章鲤，是毫無用處的摊灭。
所以有效的圖靈機必須確保能夠自身根據(jù)規(guī)則最終能切換到停機Halt狀態(tài)才行。
對于無盡這個事情败徊，《莊 子·天下篇》就講到一尺之棰,日取其半,萬世不竭帚呼，這就是一種有規(guī)則、能運行皱蹦，但不能自動停機的圖靈機算法煤杀。
繁忙的海貍Busy beaver
圖靈機本質(zhì)上是能夠自動運行的多個程序指令卡片，如下圖所示：
繁忙的海貍游戲是一個圖靈機游戲沪哺，它遵循兩個原則：
- 必須能夠自動停止Halt沈自。
- 盡可能在初始都是0的無限長紙帶上寫出更多的數(shù)字1。
在上圖中辜妓，左側(cè)每個卡片card代表一個指令枯途，也對應(yīng)一個狀態(tài)State，而紙帶上固定只有0或1兩個數(shù)字籍滴。上圖中那么就是有5個狀態(tài)（4張卡片）2個symbol元素柔袁。
1狀態(tài)繁忙的海貍 BB-1
默認Halt停機(狀態(tài)State 0)的卡片不計，只有一張卡片(狀態(tài)State 1)的繁忙海貍异逐，如下圖所示捶索。
上圖中簡化了寫法，下面0和1組成的兩行分別表示讀取的符號為0或者為1執(zhí)行的動作灰瞻。而0 101中后面三個數(shù)字分別表示把當(dāng)前位置的數(shù)字改寫為1腥例，向左移動（0向左1向右），最后一個數(shù)字表示下一狀態(tài)為1酝润。0 101即[如果讀取到0],[那么改寫為1][然后向左移動][再跳轉(zhuǎn)到狀態(tài)1]燎竖，同樣1 110表示[如果讀取到1],[那么改寫為1][然后向右移動][再跳轉(zhuǎn)到狀態(tài)0停機]。
實際上由于紙帶數(shù)字初始是0要销，讀到0构回，寫成1，向左走疏咐，狀態(tài)不變（還是轉(zhuǎn)到狀態(tài)1）纤掸，所以永遠讀取不到1，也就永遠不會進入第二行的情況浑塞，也永遠不能停下來借跪，會一直向左無限跑過去。
這樣的海貍不符合停機規(guī)則酌壕。
我們必須把第一行規(guī)則改為0 100或者0 110或者0 010,0 000掏愁，這樣才能實現(xiàn)停機歇由，但這樣只能走執(zhí)行一步，只能在紙帶上寫出1個1果港，如下圖沦泌。
有沒有更好的辦法？沒有了辛掠。無論是向左還是向右谢谦，無論是先改寫再移動還是先移動再改寫，在1state和2Symbol的情況下只能最多寫出一個1公浪。
BB-2和更多
1狀態(tài)海貍有多少種可能的走法？答案是64種船侧，當(dāng)然其中包含了很多無限循環(huán)不停機的無效走法欠气。64種走法里，能停機的最好成績是1.
關(guān)于多狀態(tài)海貍（多卡片海貍）的走法镜撩，有個公式可以套用：
可以推算出2卡片海貍共有種可能预柒。
而這20736種可能的走法中，有多少會停機袁梗？不停機的最好成績是多少宜鸯？——這些都沒法用特定算法計算，只能把這兩萬多種情況都模擬出來遮怜，然后看哪些停住了淋袖，再找出其中最好成績。
2卡片海貍即BB-2的最好成績是4锯梁，最多寫出4個1即碗，是不是很失望呢？
更失望的是BB-3陌凳，它有16777216（1600多萬）種走法剥懒，但最好成績是6。
BB-4有256乘以10的8次方那么多走法合敦，最好成績是13初橘。
BB-5則人類25年來也沒有算出確定的最好成績來，目前的最高紀(jì)錄是4098充岛。這是由于走法太多太復(fù)雜保檐，計算量太大，超級計算機也算不完崔梗。
結(jié)語
有些事情看上去簡單展东，但實際并沒有什么好的算法可以直接得出結(jié)果，只能暴力嘗試炒俱，而遇到龐大數(shù)字的時候盐肃，現(xiàn)代計算機也無能為力爪膊。
實際上每件事都會有確切算法嗎？
世上有太多需要模糊算法砸王，或者只能得到一些大約概率推盛，或者什么也得不到。
歡迎關(guān)注我的專欄( つ??ω??)つ【人工智能通識】
每個人的智能新時代
如果您發(fā)現(xiàn)文章錯誤谦铃，請不吝留言指正耘成；
如果您覺得有用，請點喜歡驹闰；
如果您覺得很有用瘪菌，歡迎轉(zhuǎn)載~
END
