忙碌的海狸
此條目沒有列出任何參考或來源。 (2020年7月23日) |
在計算機科學中,忙碌的海狸(Busy Beaver)是一個在給定參數後,尋找可能產生的最大輸出的可終止程序。忙碌的海狸遊戲包括設計一個可終止的,只輸出0或1的圖靈機,讓其在一條紙帶上儘可能多的輸出1.
包含兩個狀態的忙碌的海狸遊戲有下面兩條規則:
- 該圖靈機包括除終止態以外的兩個狀態
- 紙帶初始值都是0
玩家需要設計出可能輸出最多1的狀態轉換表格,同時也要確保圖靈機是會終止的。
能贏得n個狀態的忙碌的海狸遊戲的圖靈機,稱為第n個忙碌的海狸,或者用BB-n表示(BB是英文忙碌的海狸的縮寫)。BB-n,是在所有n個狀態的圖靈機裏面,可以輸出最多的1的。比如BB-2,可能通過6次狀態轉換輸出4個1。
忙碌的海狸遊戲是由匈牙利數學家拉多·蒂博爾在1962年發表的論文《On Non-Computable Functions》中提出的。
無限旅館的機械人
假設有一排無限房間的旅館,每個房間裏面都裝了一盞燈和一個開關。最初,所有房間的燈都是關的(狀態0)。一個機械人管家從其中某一個房間開始工作。進入房間後,它的行為只能是選擇開燈或關燈,然後移到相鄰的左邊或者右邊房間去。
這個機械人可以處於若干個預先設定的狀態中。在不同的狀態下,它會根據房間燈的開關情況,選擇不同的行為和下一步的狀態。
一個狀態的機械人
- 在「工作」態下:
- 如果房間燈是關的,開燈,移動到左邊的房間並轉換到「停止」態
- 如果房間燈是開的,關燈,移動到左邊的房間並轉換到「停止」態
- 在「停止」態下(這個遊戲必須有一個停止態,不計算在機械人狀態中):機械人停止,遊戲結束。
遊戲開始後,這個「工作」態機械人進入某個房間後,開一盞燈,然後移到左邊的房間並轉換到「停止」態,遊戲結束。我們可以驗證,無論你如何設計機械人的行為(64種可能),在只有一種狀態的約束下,機械人最多只能打開一盞燈,所以。
兩個狀態的機械人
- 在「驚恐」態下:
- 如果房間燈是關的,開燈並移動到左邊的房間去
- 如果房間燈是開的,恢復到「正常」態
- 在「正常」態下:
- 如果房間燈是開的,關燈並移動到左邊的房間去
- 其餘情況,轉變到「驚恐」態
- 在「停止」態下(這個遊戲必須有一個停止態,不計算在兩種狀態中):機械人停止,遊戲結束。
對於以上兩種狀態的機械人,如果它初始態是「驚恐」,從它進入某一個房間開放,它便會打開房間的燈然後移到左邊的房間。然後繼續開燈,向左移,無限循環下去。這樣的狀態設定是不符合忙碌的海狸必須可以終止的條件。同理,如果它的初始態是「正常」,它也會無限向左移,並不屬於忙碌的海狸。
下面我們看另外一種兩個狀態的機械人。
- 在「1」態下:
- 如果房間燈是關的,開燈,移動到右邊的房間,並轉變到「2」態
- 如果房間燈是開的,保持,移動到左邊的房間,並轉變到「2」態
- 在「2」態下:
- 如果房間燈是關的,開燈,移動到左邊的房間,並轉變到「1」態
- 如果房間燈是開的,保持,移動到左邊的房間,並轉變到「H」態
- 在「H」態下:機械人停止,遊戲結束。
這樣的狀態「1」機械人,從某個房間開始,可以進行6次移動,最終打開四盞燈(左邊2個房間,開始的房間,和右邊的一個房間),回到最左邊的房間並停止遊戲。2個狀態的機械人,全部有種行為設計,其實最多開燈的設計是4盞,所以。
3個狀態的機械人,可以通過14次移動,最多打開6盞燈。
4個狀態的機械人,可以通過107次移動,最多打開13盞燈,。
4個更多狀態的機械人,目前還不能計算出忙碌的海狸的函數值,比如目前我們猜測,但還不能確認。
相關的函數
忙碌的海狸函數
忙碌的海狸函數,又稱為BB函數,或者Radó Sigma函數,記做或者BB(n),是n個狀態的忙碌的海狸圖靈機的最大輸出。這一個增長特別快的函數,是一個非常著名的不可計算函數。Radó證明了這個函數最終會超過全部的可計算函數。
還可以定義為集合中最大的數,這個集合包括了n個狀態的2色圖靈機全部的輸出。集合的大小不超過(這是n個狀態的全部圖靈機數量)。
更普遍的,表示n個狀態,m個顏色的忙碌的海狸圖靈機。
方程值和下界
Values of S(n, m) nm2-state 3-state 4-state 5-state 6-state 7-state 2-symbol 6 21 107 176870 47 > ×1036534 7.4 > 102*101010705353 18 3-symbol 38 ≥ 112334170342540 119 > ×1014072 1.0 ??? ??? ??? 4-symbol ≥ 932964 3 > ×1013036 5.2 ??? ??? ??? ??? 5-symbol > ×10704 1.9 ??? ??? ??? ??? ??? 6-symbol > ×109866 2.4 ??? ??? ??? ??? ???
Values of Σ(n, m) nm2-state 3-state 4-state 5-state 6-state 7-state 2-symbol 4 6 13 ? 4098 > ×1018267 3.5 > 10101010705353 18 3-symbol 9 ≥ 676383 374 > ×107036 1.3 ??? ??? ??? 4-symbol ≥ 2050 > ×106518 3.7 ??? ??? ??? ??? 5-symbol > ×10352 1.7 ??? ??? ??? ??? ??? 6-symbol > ×104933 1.9 ??? ??? ??? ??? ???
例子
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Busy_Beaver_4-state_2-symbol_Run.gif/400px-Busy_Beaver_4-state_2-symbol_Run.gif)
在下面的表格中,列代表了當前的狀態,行代表了當前從紙帶讀取的標記。表格中的每一項有三個字母,分別表示向紙帶寫的標記,移動的方向和下一步的新的狀態。終止態用H代表。
每個圖靈機都從狀態A開始,紙帶無限長且初始值都是0。
結果指示: (啟始位置 1, 結束位置 1)
1-狀態, 2-標記 A 0 1RH 1 (not used)
結果: 0 0 1 0 0 (1 步, 一個 "1" )
2-狀態, 2-標記 A B 0 1RB 1LA 1 1LB 1RH
結果: 0 0 1 1 1 1 0 0 (6 步, 四個 "1")
3-狀態, 2-標記 A B C 0 1RB 0RC 1LC 1 1RH 1RB 1LA
結果: 0 0 1 1 1 1 1 1 0 0 (14 步, 六個 "1").
4-狀態, 2-標記 A B C D 0 1RB 1LA 1RH 1RD 1 1LB 0LC 1LD 0RA
結果: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 步, 十三個 "1",見圖)
5-狀態, 2-標記 (目前最大估計) A B C D E 0 1RB 1RC 1RD 1LA 1RH 1 1LC 1RB 0LE 1LD 0LA
結果: 4098 個"1"中間隔 8191 個"0"。 47,176,870 步。
6-狀態, 2-標記 (目前最大估計) A B C D E F 0 1RB 1RC 1LC 0LE 1LF 0RC 1 0LD 0RF 1LA 1RH 0RB 0RE
結果: 1 0 1 1 1 ... 1 1 1 ("10" 後面接着超過10↑↑15個"1")。超過10↑↑15 步。其中10↑↑15=1010..10是以10為底數的15層迭代冪次。