跳至內容

忙碌的海狸

維基百科,自由的百科全書

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

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

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

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

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

忙碌的海狸遊戲是由匈牙利數學家拉多·蒂博爾在1962年發表的論文《On Non-Computable Functions》中提出的。

無限旅館的機器人

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

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

一個狀態的機器人

  • 在「工作」態下:
  1. 如果房間燈是關的,開燈,移動到左邊的房間並轉換到「停止」態
  2. 如果房間燈是開的,關燈,移動到左邊的房間並轉換到「停止」態
  • 在「停止」態下(這個遊戲必須有一個停止態,不計算在機器人狀態中):機器人停止,遊戲結束。

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

兩個狀態的機器人

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

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

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

  • 在「1」態下:
  1. 如果房間燈是關的,開燈,移動到右邊的房間,並轉變到「2」態
  2. 如果房間燈是開的,保持,移動到左邊的房間,並轉變到「2」態
  • 在「2」態下:
  1. 如果房間燈是關的,開燈,移動到左邊的房間,並轉變到「1」態
  2. 如果房間燈是開的,保持,移動到左邊的房間,並轉變到「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)
n
m
2-state 3-state 4-state 5-state 6-state 7-state
2-symbol 6 21 107 47176870 > 7.4×1036534 > 102*10101018705353
3-symbol 38 119112334170342540 > 1.0×1014072 ??? ??? ???
4-symbol 3932964 > 5.2×1013036 ??? ??? ??? ???
5-symbol > 1.9×10704 ??? ??? ??? ??? ???
6-symbol > 2.4×109866 ??? ??? ??? ??? ???
Values of Σ(n, m)
n
m
2-state 3-state 4-state 5-state 6-state 7-state
2-symbol 4 6 13 4098? > 3.5×1018267 > 1010101018705353
3-symbol 9 374676383 > 1.3×107036 ??? ??? ???
4-symbol 2050 > 3.7×106518 ??? ??? ??? ???
5-symbol > 1.7×10352 ??? ??? ??? ??? ???
6-symbol > 1.9×104933 ??? ??? ??? ??? ???

例子

4-狀態,2-標記的忙碌的海狸 藍色: 紙帶 ("0" 列印為 "_"), 紅色: 狀態 (當前磁頭位置)。

在下面的表格中,列代表了當前的狀態,行代表了當前從紙帶讀取的標記。表格中的每一項有三個字母,分別表示向紙帶寫的標記,移動的方向和下一步的新的狀態。終止態用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層迭代冪次

相關詞條