忙碌的海狸

在電腦科學中，忙碌的海狸（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種可能)，在只有一種狀態的約束下，機器人最多只能打開一盞燈，所以$\Sigma(1)=1$。

### 兩個狀態的機器人

- 如果房間燈是關的，開燈並移動到左邊的房間去
- 如果房間燈是開的，恢復到「正常」態
- 如果房間燈是開的，關燈並移動到左邊的房間去
- 其餘情況，轉變到「驚恐」態
- 在「停止」態下（這個遊戲必須有一個停止態，不計算在兩種狀態中）：機器人停止，遊戲結束。

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

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

- 如果房間燈是關的，開燈，移動到右邊的房間，並轉變到「2」態
- 如果房間燈是開的，保持，移動到左邊的房間，並轉變到「2」態
- 如果房間燈是關的，開燈，移動到左邊的房間，並轉變到「1」態
- 如果房間燈是開的，保持，移動到左邊的房間，並轉變到「H」態
- 在「H」態下：機器人停止，遊戲結束。

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

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

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

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

## 相關的函數

### 忙碌的海狸函數

忙碌的海狸函數，又稱為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個顏色的忙碌的海狸圖靈機。

### 方程值和下界

m｜2-state｜3-state｜4-state｜5-state｜6-state｜7-state

2-symbol｜6｜21｜107｜47176870｜> 7.4×10^36534｜> 102、10101018705353

3-symbol｜38｜≥ 119112334170342540｜> 1.0×10^14072｜???｜???｜???

4-symbol｜≥ 3932964｜> 5.2×10^13036｜???｜???｜???｜???

5-symbol｜> 1.9×10^704｜???｜???｜???｜???｜???

6-symbol｜> 2.4×10^9866｜???｜???｜???｜???｜???

m｜2-state｜3-state｜4-state｜5-state｜6-state｜7-state

2-symbol｜4｜6｜13｜4098?｜> 3.5×10^18267｜> 1010101018705353

3-symbol｜9｜≥ 374676383｜> 1.3×10^7036｜???｜???｜???

4-symbol｜≥ 2050｜> 3.7×10^6518｜???｜???｜???｜???

5-symbol｜> 1.7×10^352｜???｜???｜???｜???｜???

6-symbol｜> 1.9×10^4933｜???｜???｜???｜???｜???

## 例子

<image>

在下面的表格中，列代表了當前的狀態，行代表了當前從紙帶讀取的標記。表格中的每一項有三個字母，分別表示向紙帶寫的標記，移動的方向和下一步的新的狀態。終止態用H代表。

每個圖靈機都從狀態A開始，紙帶無限長且初始值都是0。

結果指示: (啟始位置 1, 結束位置 1)

A

0｜1RH

1｜(not used)

結果: 0 0 1 0 0 (1 步, 一個 "1" )

A｜B

0｜1RB｜1LA

1｜1LB｜1RH

結果: 0 0 1 1 1 1 0 0 (6 步, 四個 "1")

A｜B｜C

0｜1RB｜0RC｜1LC

1｜1RH｜1RB｜1LA

結果: 0 0 1 1 1 1 1 1 0 0 (14 步, 六個 "1").

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",見圖)

A｜B｜C｜D｜E

0｜1RB｜1RC｜1RD｜1LA｜1RH

1｜1LC｜1RB｜0LE｜1LD｜0LA

結果: 4098 個"1"中間隔 8191 個"0"。47,176,870 步。

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層迭代冪次。