繁忙的海狸功能是否爲n狀態繁忙海狸遊戲獨特？

對於給定的n狀態busy beaver game，busy beaver function是唯一的，還是可能有多個函數具有相同的最大分數？也許它沒有被證明任何方式？繁忙的海狸功能是否爲n狀態繁忙海狸遊戲獨特？

來源

2011-09-06 Daniel

一個非常有趣的問題，但也許更適合http://cstheory.stackexchange.com/？ –

正如@PengOne指出的那樣，該功能確實是唯一的。它是一個完全定義的N - > N離散函數。

但是，根據您的公式（「或者可能會有多個函數具有相同的最大分數」），還可以理解您想知道是否有多個繁忙的海狸鸚鵡提供相同的最大值。如果是這樣的話，那麼是的，至少有兩個忙碌的海狸給予一個N，一個是通過簡單地顛倒輪班而從另一個構造的。

來源

2011-09-06 14:54:44

那麼爲什麼這並不意味着函數是不唯一的？ – Daniel

沒關係。我明白。因爲映射是相同的，只是中間步驟是不同的。謝謝。 – Daniel

@丹尼爾，我想你正在使用一個非標準的術語。標準術語（例如，在您鏈接的維基百科文章中使用的）是繁忙的海狸功能是告訴您所有n-state圖靈機的最高分數的函數。只有一個功能。但是，有多個圖靈機達到了這個最大值（如Luchian Grigore提到的）。這些機器可以被認爲是圖靈機語言中的程序;你似乎稱他們爲這裏造成混亂的功能。 – sligocki

是的。

繁忙海狸函數被限定爲使得

\Sigma(n) = max { \sigma(M) | M is a halting n-state 2-symbol Turing machine}

如果它存在，其中它不（雷達表證明瞭這）最大是獨一無二的。這只是一個數字。因此\ Sigma（n）也是唯一的，所以離散函數\ Sigma：N - > N也是唯一的。可能有多種方法將\西格瑪延伸到一個連續的功能，但爲什麼有人想要這樣做超出了我的想象。

可以計算\ Sigma的小值;查看OEIS entry已知的最大值。

來源

2011-09-06 14:34:54 PengOne

這已經是很久以前問過，但我發現這個有趣的：http://www.win.tue.nl/~wijers/shallit.pdf

另外，我編碼的野蠻強制三態忙海狸問題的算法，它給了我大約22非產生6個符號的對稱配置（連續與否）。這意味着，如果您認爲可以交換狀態1和狀態2，並且與第一個轉換相反，則可能有60個配置。

但是，這只是生產符號的數量，而不是'最長的執行'。

來源

2014-04-15 20:32:27

繁忙的海狸功能是否爲n狀態繁忙海狸遊戲獨特？

回答

相關問題