忙碌的海狸

在計算機科學中，忙碌的海狸（Busy Beaver）是一個在給定參數後，尋找可能產生的最大輸出的可終止程序。忙碌的海狸遊戲包括設計一個可終止的，只輸出0或1的圖靈機，讓其在一條紙帶上儘可能多的輸出1.

包含兩個狀態的忙碌的海狸遊戲有下面兩條規則：

該圖靈機包括除終止態以外的兩個狀態
紙帶初始值都是0

玩家需要設計出可能輸出最多1的狀態轉換表格，同時也要確保圖靈機是會終止的。

能贏得n個狀態的忙碌的海狸遊戲的圖靈機，稱為第n個忙碌的海狸，或者用BB-n表示(BB是英文忙碌的海狸的縮寫)。BB-n，是在所有n個狀態的圖靈機裡面，可以輸出最多的1的。比如BB-2，可能通過6次狀態轉換輸出4個1。

忙碌的海狸遊戲是由匈牙利的數學家Tibor Radó在1962年發表的論文《On Non-Computable Functions》中提出的。

無限旅館的機器人[編輯]

假設有一排無限房間的旅館，每個房間裡面都裝了一盞燈和一個開關。最初，所有房間的燈都是關的（狀態0）。一個機器人管家從其中某一個房間開始工作。進入房間後，它的行為只能是選擇開燈或關燈，然後移到相鄰的左邊或者右邊房間去。

這個機器人可以處於若干個預先設定的狀態中。在不同的狀態下，它會根據房間燈的開關情況，選擇不同的行為和下一步的狀態。

一個狀態的機器人[編輯]

在「工作」態下：

如果房間燈是關的，開燈，移動到左邊的房間並轉換到「停止」態
如果房間燈是開的，關燈，移動到左邊的房間並轉換到「停止」態

在「停止」態下（這個遊戲必須有一個停止態，不計算在機器人狀態中）：機器人停止，遊戲結束。

遊戲開始後，這個「工作」態機器人進入某個房間後，開一盞燈，然後移到左邊的房間並轉換到「停止」態，遊戲結束。我們可以驗證，無論你如何設計機器人的行為(64種可能)，在只有一種狀態的約束下，機器人最多只能打開一盞燈，所以 $\Sigma (1)=1$ 。

兩個狀態的機器人[編輯]

在「驚恐」態下：

如果房間燈是關的，開燈並移動到左邊的房間去
如果房間燈是開的，恢復到「正常」態

在「正常」態下：

如果房間燈是開的，關燈並移動到左邊的房間去
其餘情況，轉變到「驚恐」態

在「停止」態下（這個遊戲必須有一個停止態，不計算在兩種狀態中）：機器人停止，遊戲結束。

對於以上兩種狀態的機器人，如果它初始態是「驚恐」，從它進入某一個房間開放，它便會打開房間的燈然後移到左邊的房間。然後繼續開燈，向左移，無限循環下去。這樣的狀態設定是不符合忙碌的海狸必須可以終止的條件。同理，如果它的初始態是「正常」，它也會無限向左移，並不屬於忙碌的海狸。

下面我們看另外一種兩個狀態的機器人。

在「1」態下：

如果房間燈是關的，開燈，移動到右邊的房間，並轉變到「2」態
如果房間燈是開的，保持，移動到左邊的房間，並轉變到「2」態

在「2」態下：

如果房間燈是關的，開燈，移動到左邊的房間，並轉變到「1」態
如果房間燈是開的，保持，移動到左邊的房間，並轉變到「H」態

在「H」態下：機器人停止，遊戲結束。

這樣的狀態「1」機器人，從某個房間開始，可以進行6次移動，最終打開四盞燈（左邊2個房間，開始的房間，和右邊的一個房間），回到最左邊的房間並停止遊戲。2個狀態的機器人，全部有 $(2\times 2\times 3)^{2\times 2}=20736$ 種行為設計，其實最多開燈的設計是4盞，所以 $\Sigma (2)=4$ 。

3個狀態的機器人，可以通過14次移動，最多打開6盞燈 $\Sigma (3)=6$ 。

4個狀態的機器人，可以通過107次移動，最多打開13盞燈， $\Sigma (4)=13$ 。

4個更多狀態的機器人，目前還不能計算出忙碌的海狸的函數值，比如目前我們猜測 $\Sigma (5)\geqslant 4098$ ，但還不能確認。

相關的函數[編輯]

忙碌的海狸函數[編輯]

忙碌的海狸函數，又稱為BB函數，或者Radó Sigma函數，記做 $\Sigma (n)$ 或者BB(n),是n個狀態的忙碌的海狸圖靈機的最大輸出。這一個增長特別快的函數，是一個非常著名的不可計算函數。Radó證明了這個函數最終會超過全部的可計算函數。

$\Sigma (n)$ 還可以定義為集合 $T=\{n_{1},n_{2},\cdots ,n_{k}\}$ 中最大的數，這個集合包括了n個狀態的2色圖靈機全部的輸出。集合 $T$ 的大小不超過 $(4n+4)^{2n}$ （這是n個狀態的全部圖靈機數量）。

更普遍的， $\Sigma (n,m)$ 表示n個狀態，m個顏色的忙碌的海狸圖靈機。

方程值和下界[編輯]

Values of S(n, m)
n m	2-state	3-state	4-state	5-state	6-state	7-state
2-symbol	6	21	107	7007471768700000000♠47176870?	> 9000000000000000000♠7.4×10³⁶⁵³⁴	> 10^{2*10^{10^{10^{7007187053530000000♠18705353}}}}
3-symbol	38	≥ 7017119112334170342♠119112334170342540	> 9000000000000000000♠1.0×10¹⁴⁰⁷²	???	???	???
4-symbol	≥ 7006393296400000000♠3932964	> 9000000000000000000♠5.2×10¹³⁰³⁶	???	???	???	???
5-symbol	> 9000000000000000000♠1.9×10⁷⁰⁴	???	???	???	???	???
6-symbol	> 9000000000000000000♠2.4×10⁹⁸⁶⁶	???	???	???	???	???

Values of Σ(n, m)
n m	2-state	3-state	4-state	5-state	6-state	7-state
2-symbol	4	6	13	7003409800000000000♠4098?	> 9000000000000000000♠3.5×10¹⁸²⁶⁷	> 10^{10^{10^{10^{7007187053530000000♠18705353}}}}
3-symbol	9	≥ 7008374676383000000♠374676383	> 9000000000000000000♠1.3×10⁷⁰³⁶	???	???	???
4-symbol	≥ 7003205000000000000♠2050	> 9000000000000000000♠3.7×10⁶⁵¹⁸	???	???	???	???
5-symbol	> 9000000000000000000♠1.7×10³⁵²	???	???	???	???	???
6-symbol	> 9000000000000000000♠1.9×10⁴⁹³³	???	???	???	???	???

例子[編輯]

在下面的表格中，列代表了當前的狀態，行代表了當前從紙帶讀取的標記。表格中的每一項有三個字母，分別表示向紙帶寫的標記，移動的方向和下一步的新的狀態。終止態用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=10^{10^{.^.¹⁰}}是以10為底數的15層迭代冪次。