忙碌海狸函数 - 版本历史

Tabelog：文字替换 -“BMS”替换为“BMS”

2025-08-30T13:33:20Z

文字替换 -“BMS”替换为“BMS”

←上一版本		2025年8月30日 (六) 21:33的版本
第182行：		第182行：
	Rohan Ridenour 证明了 BB(1015) 超过了 [[Loader 数]]<ref>Cats Are Fully (n.d.). Metamath turing machines. ''(EB/OL), Github''. Available at: https://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe</ref>。HypCos 在他的作品《大数入门》中提到 BB(160) 已经大于 Loader 数，但没有给出出处。		Rohan Ridenour 证明了 BB(1015) 超过了 [[Loader 数]]<ref>Cats Are Fully (n.d.). Metamath turing machines. ''(EB/OL), Github''. Available at: https://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe</ref>。HypCos 在他的作品《大数入门》中提到 BB(160) 已经大于 Loader 数，但没有给出出处。

	据信 <math>BB(150)>f_{SHO}(10\uparrow\uparrow15)</math>，其中 [[SHO]] 是 [[~~Bashicu矩阵\|~~BMS]] 的极限。<ref>Morphett, (n.d.). Turing machine simulator. ''(EB/OL)''. Available at: https://morphett.info/turing/turing.html?c95a199c8e8a3dd56452f8b7e28fabbf</ref>		据信 <math>BB(150)>f_{SHO}(10\uparrow\uparrow15)</math>，其中 [[SHO]] 是 [[BMS]] 的极限。<ref>Morphett, (n.d.). Turing machine simulator. ''(EB/OL)''. Available at: https://morphett.info/turing/turing.html?c95a199c8e8a3dd56452f8b7e28fabbf</ref>

	=== 相关函数 ===		=== 相关函数 ===

2025年8月23日 (六) 01:33 Z

2025-08-23T01:33:53Z

←上一版本		2025年8月23日 (六) 09:33的版本
第52行：		第52行：

	=== 取值 ===		=== 取值 ===
	很难证明特定的图灵机是否恰好是一只忙碌的海狸。n 状态的 2 色图灵机有 <math>(4n+4)^{2n}</math> ~~台，这实在太多了。当然，通过利用对称性和具有不可达状态的图灵机，这一数量可降至~~ <math>(2n-1)(4n)^{2n-2}</math><ref>Mrob. (n.d.). Notes on Busy Beaver Function. ''(EB/OL), Mrob''. Available at: https://mrob.com/pub/math/ln-notes1-4.html</ref>，从而立即排除了最平凡的图灵机。然而计算出准确值依然是苦难的，但我们可以想办法给出一些下界。有两种常规方法可以解决该问题：自下而上技术（适用于较小的 n）和自上而下技术（适用于较大的 n）。		很难证明特定的图灵机是否恰好是一只忙碌的海狸。n 状态的 2 色图灵机有 <math>(4n+4)^{2n}</math> 台，这实在太多了。当然，通过利用对称性和排除具有不可达状态的图灵机，这一数量可降至 <math>(2n-1)(4n)^{2n-2}</math><ref>Mrob. (n.d.). Notes on Busy Beaver Function. ''(EB/OL), Mrob''. Available at: https://mrob.com/pub/math/ln-notes1-4.html</ref>，从而立即排除了最平凡的图灵机。然而计算出准确值依然是困难的，但我们可以想办法给出一些下界。有两种常规方法可以解决该问题：自下而上技术（适用于较小的 n）和自上而下技术（适用于较大的 n）。

	对于自下而上技术：		对于自下而上技术：

2025年8月20日 (三) 08:23 Z

2025-08-20T08:23:32Z

←上一版本		2025年8月20日 (三) 16:23的版本
第213行：		第213行：

	== 参考资料 ==		== 参考资料 ==
	<references />		<references />{{默认排序:相关问题}}
	[[分类:记号]]		[[分类:记号]]

2025年8月6日 (三) 10:01 Tabelog

2025-08-06T10:01:06Z

←上一版本		2025年8月6日 (三) 18:01的版本
第49行：		第49行：
	我们定义忙碌海狸函数如下：		我们定义忙碌海狸函数如下：

	一个能够停机的 2 色，n 状态图灵机，从全 0 的纸带开始，所能够扫过的最大格子数定义为 <math>BB(n)</math> 或者 <math>\Sigma(n)</math>。<ref>Rado, T. (1962). On Non-Computable Functions. ''Bell System Technical J''. 41, 877-884. https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x</ref>我们称这样的图灵机是“忙碌的海狸”。		一个能够停机的 2 色，n 状态图灵机，从全 0 的纸带开始，所能够扫过的最大格子数定义为 <math>BB(n)</math> 或者 <math>\Sigma(n)</math>。<ref name=":0">Rado, T. (1962). On Non-Computable Functions. ''Bell System Technical J'', Vol. 41, pp. 877-884. Available at https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x</ref>我们称这样的图灵机是“忙碌的海狸”。

	=== 取值 ===		=== 取值 ===
	很难证明特定的图灵机是否恰好是一只忙碌的海狸。n 状态的 2 色图灵机有 <math>(4n+4)^{2n}</math> 台，这实在太多了。当然，通过利用对称性和具有不可达状态的图灵机，这一数量可降至 <math>(2n-1)(4n)^{2n-2}</math><ref>Mrob. Notes on Busy Beaver Function. ''(EB/OL), Mrob''. https://mrob.com/pub/math/ln-notes1-4.html</ref>，从而立即排除了最平凡的图灵机。然而计算出准确值依然是苦难的，但我们可以想办法给出一些下界。有两种常规方法可以解决该问题：自下而上技术（适用于较小的 n）和自上而下技术（适用于较大的 n）。		很难证明特定的图灵机是否恰好是一只忙碌的海狸。n 状态的 2 色图灵机有 <math>(4n+4)^{2n}</math> 台，这实在太多了。当然，通过利用对称性和具有不可达状态的图灵机，这一数量可降至 <math>(2n-1)(4n)^{2n-2}</math><ref>Mrob. (n.d.). Notes on Busy Beaver Function. ''(EB/OL), Mrob''. Available at: https://mrob.com/pub/math/ln-notes1-4.html</ref>，从而立即排除了最平凡的图灵机。然而计算出准确值依然是苦难的，但我们可以想办法给出一些下界。有两种常规方法可以解决该问题：自下而上技术（适用于较小的 n）和自上而下技术（适用于较大的 n）。

	对于自下而上技术：		对于自下而上技术：
第75行：		第75行：
	对于 BB(1)，显然，它只有立刻停机一种可能。因此 <math>BB(1)=1</math>。		对于 BB(1)，显然，它只有立刻停机一种可能。因此 <math>BB(1)=1</math>。

	BB(2) 所对应的图灵机为：<ref~~>Rado, T. (1962). On non-computable functions. ''The Bell System Technical Journal'', vol. 41, no. 3, pp. 877-884.<~~/~~ref~~>		BB(2) 所对应的图灵机为：<ref name=":0" />

	{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
第95行：		第95行：
	[[文件:Busy-beaver-three-states-new.png\|frame\|right\|200px\|三状态图灵机]]		[[文件:Busy-beaver-three-states-new.png\|frame\|right\|200px\|三状态图灵机]]

	BB(3) 所对应的图灵机是<ref>Lin, & Rado, T. (1965). Computer Studies of Turing Machine Problems. ''Journal for the Association of Computing Machinery'', ~~vol~~. 12, no. 2, pp. 196-212.</ref>		BB(3) 所对应的图灵机是<ref>Lin., & Rado, T. (1965). Computer Studies of Turing Machine Problems. ''Journal for the Association of Computing Machinery'', Vol. 12, No. 2, pp. 196-212.</ref>

	{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
第118行：		第118行：
	[[文件:Busy-beaver-four-states-new.png\|frame\|right\|200px\|四状态图灵机]]		[[文件:Busy-beaver-four-states-new.png\|frame\|right\|200px\|四状态图灵机]]

	BB(4) 所对应的图灵机是<ref>Brady, A. H. (1975). Solution of the non-computable "Busy Beaver" game for k=4. ~~Abstracts for~~ ''ACM Computer Science Conference'' ~~(Washington DC~~, ~~1975), p~~. 27~~, ACM~~.</ref>		BB(4) 所对应的图灵机是<ref>Brady, A. H. (1975). Solution of the non-computable "Busy Beaver" game for k=4. ''ACM Computer Science Conference'', pp. 27.</ref>

	{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
第142行：		第142行：
	可得 BB(4) = 13。		可得 BB(4) = 13。

	BB(5) 所对应的图灵机是<ref>Marxen, H., & Buntrock, J. (1990). Attacking the Busy Beaver 5 Bulletin. ''EATCS'', 40, pp. 247-251.</ref><ref>The Busy Beaver Challenge (2024). We have proved "BB(5) = 47,176,870". ''(EB/OL), The Busy Beaver Challenge''. https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237</ref>		BB(5) 所对应的图灵机是<ref>Marxen, H., & Buntrock, J. (1990). Attacking the Busy Beaver 5 Bulletin. ''EATCS'', Vol. 40, pp. 247-251.</ref><ref>The Busy Beaver Challenge (2024). We have proved "BB(5) = 47,176,870". ''(EB/OL), The Busy Beaver Challenge''. Available at: https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237</ref>
	{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
第170行：		第170行：
	对于更之后的 BB 函数，我们还未计算出精确值。我们有		对于更之后的 BB 函数，我们还未计算出精确值。我们有

	<math>BB(6)\geq2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow9</math><ref>The Busy Beaver Challenge. 1RB1RA 1RC--- 1LD0RF 1RA0LE 0LD1RC 1RA0RE. ''(EB/OL), The Busy Beaver Challenge''. https://wiki.bbchallenge.org/wiki/1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE</ref>		<math>BB(6)\geq2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow9</math><ref>The Busy Beaver Challenge (n.d.). 1RB1RA 1RC--- 1LD0RF 1RA0LE 0LD1RC 1RA0RE. ''(EB/OL), The Busy Beaver Challenge''. Available at: https://wiki.bbchallenge.org/wiki/1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE</ref>

	<math>BB(7)\geq2\uparrow^{11}2\uparrow^{11}3</math><ref>Google Groups. Busy Beaver Discuss - l5vKduGGKJc. ''(EB/OL)''. https://groups.google.com/g/busy-beaver-discuss/c/l5vKduGGKJc</ref>		<math>BB(7)\geq2\uparrow^{11}2\uparrow^{11}3</math><ref>Google Groups (n.d.). Busy Beaver Discuss - l5vKduGGKJc. ''(EB/OL)''. Available at: https://groups.google.com/g/busy-beaver-discuss/c/l5vKduGGKJc</ref>

	Milton Green 证明了<math>BB(2n)\gg 3\uparrow^{n-2}3</math>。<ref>Green, M. (2013). A lower bound RADO's sigma function for binary turing machines. ''~~doi~~''. ~~https:~~/~~/doi~~.~~ieeecomputersociety~~.~~org/~~10.1109/SWCT.1964.3</ref>BB(6) 已经远远大于 27，因此这个下界是很弱的。		Milton Green 证明了<math>BB(2n)\gg 3\uparrow^{n-2}3</math>。<ref>Green, M. (2013). A lower bound RADO's sigma function for binary turing machines. ''(n.p.)'', [[Doi:10.1109/SWCT.1964.3\|doi:10.1109/SWCT.1964.3]].</ref>BB(6) 已经远远大于 27，因此这个下界是很弱的。

	[[葛立恒数]]是一个非常著名的大数，但它在一些较小的 n 就被 BB(n) 超越。目前最新的成果是 Daniel Nagaj 证明了 BB(14)>G，该证明被 Shawn Ligocki 所确认。<ref>Sligochi (2022). BB(16) > Graham's Number. ''(EB/OL)''. https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>		[[葛立恒数]]是一个非常著名的大数，但它在一些较小的 n 就被 BB(n) 超越。目前最新的成果是 Daniel Nagaj 证明了 BB(14)>G，该证明被 Shawn Ligocki 所确认。<ref>Sligochi (2022). BB(16) > Graham's Number. ''(EB/OL)''. Available at: https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>

	对于一些较大的 n，Wythagoras 证明了<math>BB(38)>f_{\omega\times2}(67)</math>、<math>BB(64)>f_{\omega^2}(4098)</math> 以及<math>BB(85)>f_{\varepsilon_0}(1907)</math>。		对于一些较大的 n，Wythagoras 证明了<math>BB(38)>f_{\omega\times2}(67)</math>、<math>BB(64)>f_{\omega^2}(4098)</math> 以及<math>BB(85)>f_{\varepsilon_0}(1907)</math>。

	Rohan Ridenour 证明了 BB(1015) 超过了 [[~~Loader数\|~~Loader 数]]<ref>Cats Are Fully. Metamath turing machines. ''(EB/OL), Github''. https://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe</ref>。HypCos 在他的作品《大数入门》中提到 BB(160) 已经大于 Loader 数，但没有给出出处。		Rohan Ridenour 证明了 BB(1015) 超过了 [[Loader 数]]<ref>Cats Are Fully (n.d.). Metamath turing machines. ''(EB/OL), Github''. Available at: https://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe</ref>。HypCos 在他的作品《大数入门》中提到 BB(160) 已经大于 Loader 数，但没有给出出处。

	据信 <math>BB(150)>f_{SHO}(10\uparrow\uparrow15)</math>，其中 [[SHO]] 是 [[Bashicu矩阵\|BMS]] 的极限。<ref>Morphett. Turing machine simulator. ''(EB/OL)''. https://morphett.info/turing/turing.html?c95a199c8e8a3dd56452f8b7e28fabbf</ref>		据信 <math>BB(150)>f_{SHO}(10\uparrow\uparrow15)</math>，其中 [[SHO]] 是 [[Bashicu矩阵\|BMS]] 的极限。<ref>Morphett, (n.d.). Turing machine simulator. ''(EB/OL)''. Available at: https://morphett.info/turing/turing.html?c95a199c8e8a3dd56452f8b7e28fabbf</ref>

	== 相关函数 ==		=== 相关函数 ===

	=== 疯狂青蛙函数 S(n) ===		==== 疯狂青蛙函数 S(n) ====
	Tibor Radó 引入了另一个不可计算的快速增长函数 S(n)，根据 n 状态 2 色图灵机在停止前所走的最多步数来定义。有时忙碌海狸函数会被认为是最大移动步数。为避免歧义，S(n) 又称为疯狂青蛙函数。		Tibor Radó 引入了另一个不可计算的快速增长函数 S(n)，根据 n 状态 2 色图灵机在停止前所走的最多步数来定义。有时忙碌海狸函数会被认为是最大移动步数。为避免歧义，S(n) 又称为疯狂青蛙函数。

	由于图灵机运行时会左右摇摆，所以 <math>S(n)\geq BB(n)</math>。一个忙碌的海狸也不一定是一个疯狂的青蛙。已经证明，疯狂青蛙函数与忙碌海狸函数具有相当的增长率。		由于图灵机运行时会左右摇摆，所以 <math>S(n)\geq BB(n)</math>。一个忙碌的海狸也不一定是一个疯狂的青蛙。已经证明，疯狂青蛙函数与忙碌海狸函数具有相当的增长率。

	=== 二元忙碌海狸 BB(m,n) ===		==== 二元忙碌海狸 BB(m,n) ====
	我们定义二元忙碌海狸函数 BB(m,n) 为一个能够停机的 m 色，n 状态图灵机，从全 0 的纸带开始，所能够扫过的最大格子数。		我们定义二元忙碌海狸函数 BB(m,n) 为一个能够停机的 m 色，n 状态图灵机，从全 0 的纸带开始，所能够扫过的最大格子数。

	类似的，也可以定义二元疯狂青蛙函数。		类似的，也可以定义二元疯狂青蛙函数。

	== 传言 ==		=== 传言 ===
	有一些资料声称哥德巴赫猜想已经被证明最大反例一定小于 BB(27)，这实际上是错误的。正确的说法是，我们找到了一个 27 状态的 2 色图灵机<ref>Anonymous. list27.txt. ''(EB/OL), Github''. https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6</ref>，它停机当且仅当哥德巴赫猜想不成立。类似的，还存在一个验证黎曼猜想的图灵机，有 5372 个状态。这两个图灵机其实是告诉我们世界上存在有限时间内可以证明哥德巴赫猜想和黎曼猜想的程序，它们至少保证了哥德巴赫猜想和黎曼猜想是可被证明的，而不会是那种“不可证明”的命题。		有一些资料声称哥德巴赫猜想已经被证明最大反例一定小于 BB(27)，这实际上是错误的。正确的说法是，我们找到了一个 27 状态的 2 色图灵机<ref>(Anonymous). (n.d.). list27.txt. ''(EB/OL), Github''. Available at: https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6</ref>，它停机当且仅当哥德巴赫猜想不成立。类似的，还存在一个验证黎曼猜想的图灵机，有 5372 个状态。这两个图灵机其实是告诉我们世界上存在有限时间内可以证明哥德巴赫猜想和黎曼猜想的程序，它们至少保证了哥德巴赫猜想和黎曼猜想是可被证明的，而不会是那种“不可证明”的命题。

	Yedidia 还写了这样一个程序，它验证这样一个命题: [[ZFC公理体系\|ZF]] 是[[一致性\|一致]]（自洽）的，它有 7918 个状态。		Yedidia 还写了这样一个程序，它验证这样一个命题: [[ZFC公理体系\|ZF]] 是[[一致性\|一致]]（自洽）的，它有 7918 个状态。

	== 趣事 ==		=== 趣事 ===
	曹知秋找到了以下三段话，读起来令人忍俊不禁.		曹知秋找到了以下三段话，读起来令人忍俊不禁.
	<blockquote>		<blockquote>

Tabelog：修正参考资料

2025-07-30T05:51:04Z

修正参考资料

←上一版本		2025年7月30日 (三) 13:51的版本
第49行：		第49行：
	我们定义忙碌海狸函数如下：		我们定义忙碌海狸函数如下：

	一个能够停机的 2 色，n 状态图灵机，从全 0 的纸带开始，所能够扫过的最大格子数定义为 <math>BB(n)</math> 或者 <math>\Sigma(n)</math>。<ref>Rado, T (1962). [https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x ~~On Non-Computable Functions]. ''Bell System Technical J''. 41, 877-884.~~</ref>我们称这样的图灵机是“忙碌的海狸”。		一个能够停机的 2 色，n 状态图灵机，从全 0 的纸带开始，所能够扫过的最大格子数定义为 <math>BB(n)</math> 或者 <math>\Sigma(n)</math>。<ref>Rado, T. (1962). On Non-Computable Functions. ''Bell System Technical J''. 41, 877-884. https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x</ref>我们称这样的图灵机是“忙碌的海狸”。

	=== 取值 ===		=== 取值 ===
	很难证明特定的图灵机是否恰好是一只忙碌的海狸。n 状态的 2 色图灵机有 <math>(4n+4)^{2n}</math> 台，这实在太多了。当然，通过利用对称性和具有不可达状态的图灵机，这一数量可降至 <math>(2n-1)(4n)^{2n-2}</math><ref>[https://mrob.com/pub/math/ln-notes1-4.html ~~Notes on Busy Beaver Function]~~</ref>，从而立即排除了最平凡的图灵机。然而计算出准确值依然是苦难的，但我们可以想办法给出一些下界。有两种常规方法可以解决该问题：自下而上技术（适用于较小的 n）和自上而下技术（适用于较大的 n）。		很难证明特定的图灵机是否恰好是一只忙碌的海狸。n 状态的 2 色图灵机有 <math>(4n+4)^{2n}</math> 台，这实在太多了。当然，通过利用对称性和具有不可达状态的图灵机，这一数量可降至 <math>(2n-1)(4n)^{2n-2}</math><ref>Mrob. Notes on Busy Beaver Function. ''(EB/OL), Mrob''. https://mrob.com/pub/math/ln-notes1-4.html</ref>，从而立即排除了最平凡的图灵机。然而计算出准确值依然是苦难的，但我们可以想办法给出一些下界。有两种常规方法可以解决该问题：自下而上技术（适用于较小的 n）和自上而下技术（适用于较大的 n）。

	对于自下而上技术：		对于自下而上技术：
第75行：		第75行：
	对于 BB(1)，显然，它只有立刻停机一种可能。因此 <math>BB(1)=1</math>。		对于 BB(1)，显然，它只有立刻停机一种可能。因此 <math>BB(1)=1</math>。

	BB(2) 所对应的图灵机为：<ref>Rado, On non-computable functions. The Bell System Technical Journal, vol. 41, no. 3, pp. 877-884~~, May 1962, for Sigma(1) and Sigma(2)~~</ref>		BB(2) 所对应的图灵机为：<ref>Rado, T. (1962). On non-computable functions. ''The Bell System Technical Journal'', vol. 41, no. 3, pp. 877-884.</ref>

	{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
第95行：		第95行：
	[[文件:Busy-beaver-three-states-new.png\|frame\|right\|200px\|三状态图灵机]]		[[文件:Busy-beaver-three-states-new.png\|frame\|right\|200px\|三状态图灵机]]

	BB(3) 所对应的图灵机是<ref>Lin & Rado. Computer Studies of Turing Machine Problems. Journal for the Association of Computing Machinery, vol. 12, no. 2, pp. 196-212~~, April 1965, for Sigma(3)~~</ref>		BB(3) 所对应的图灵机是<ref>Lin, & Rado, T. (1965). Computer Studies of Turing Machine Problems. ''Journal for the Association of Computing Machinery'', vol. 12, no. 2, pp. 196-212.</ref>

	{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
第118行：		第118行：
	[[文件:Busy-beaver-four-states-new.png\|frame\|right\|200px\|四状态图灵机]]		[[文件:Busy-beaver-four-states-new.png\|frame\|right\|200px\|四状态图灵机]]

	BB(4) 所对应的图灵机是<ref>A. H. ~~Brady~~. Solution of the non-computable "Busy Beaver" game for k=4. Abstracts for ACM Computer Science Conference (Washington DC, 1975), p. 27, ACM~~, 1975, for Sigma(4)~~.</ref>		BB(4) 所对应的图灵机是<ref>Brady, A. H. (1975). Solution of the non-computable "Busy Beaver" game for k=4. Abstracts for ''ACM Computer Science Conference'' (Washington DC, 1975), p. 27, ACM.</ref>

	{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
第142行：		第142行：
	可得 BB(4) = 13。		可得 BB(4) = 13。

	BB(5) 所对应的图灵机是<ref>H. ~~Marxen and~~ J. ~~Buntrock~~. Attacking the Busy Beaver 5 Bulletin ~~of the~~ EATCS, 40, pp. 247-251~~, February 1990, for Sigma(5)~~.</ref><ref>~~[July 2nd~~ 2024~~] [~~https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 ~~We have proved "BB(5) = 47,176,870"] - News - The Busy Beaver Challenge~~</ref>		BB(5) 所对应的图灵机是<ref>Marxen, H., & Buntrock, J. (1990). Attacking the Busy Beaver 5 Bulletin. ''EATCS'', 40, pp. 247-251.</ref><ref>The Busy Beaver Challenge (2024). We have proved "BB(5) = 47,176,870". ''(EB/OL), The Busy Beaver Challenge''. https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237</ref>
	{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
第170行：		第170行：
	对于更之后的 BB 函数，我们还未计算出精确值。我们有		对于更之后的 BB 函数，我们还未计算出精确值。我们有

	<math>BB(6)\geq2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow9</math><ref>https://wiki.bbchallenge.org/wiki/1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE</ref>		<math>BB(6)\geq2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow9</math><ref>The Busy Beaver Challenge. 1RB1RA 1RC--- 1LD0RF 1RA0LE 0LD1RC 1RA0RE. ''(EB/OL), The Busy Beaver Challenge''. https://wiki.bbchallenge.org/wiki/1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE</ref>

	<math>BB(7)\geq2\uparrow^{11}2\uparrow^{11}3</math><ref>https://groups.google.com/g/busy-beaver-discuss/c/l5vKduGGKJc</ref>		<math>BB(7)\geq2\uparrow^{11}2\uparrow^{11}3</math><ref>Google Groups. Busy Beaver Discuss - l5vKduGGKJc. ''(EB/OL)''. https://groups.google.com/g/busy-beaver-discuss/c/l5vKduGGKJc</ref>

	Milton Green 证明了<math>BB(2n)\gg 3\uparrow^{n-2}3</math>。<ref>Green, ~~Milton~~. [https://doi.ieeecomputersociety.org/10.1109/SWCT.1964.3 ~~A lower bound RADO's sigma function for binary turing machines]. Retrieved 2013-05-07.~~</ref>BB(6) 已经远远大于 27，因此这个下界是很弱的。		Milton Green 证明了<math>BB(2n)\gg 3\uparrow^{n-2}3</math>。<ref>Green, M. (2013). A lower bound RADO's sigma function for binary turing machines. ''doi''. https://doi.ieeecomputersociety.org/10.1109/SWCT.1964.3</ref>BB(6) 已经远远大于 27，因此这个下界是很弱的。

	[[葛立恒数]]是一个非常著名的大数，但它在一些较小的 n 就被 BB(n) 超越。目前最新的成果是 Daniel Nagaj 证明了 BB(14)>G，该证明被 Shawn Ligocki 所确认。<ref>[https://www.sligocki.com/2022/07/11/bb-16-graham.html ~~BB(16) > Graham's Number]~~</ref>		[[葛立恒数]]是一个非常著名的大数，但它在一些较小的 n 就被 BB(n) 超越。目前最新的成果是 Daniel Nagaj 证明了 BB(14)>G，该证明被 Shawn Ligocki 所确认。<ref>Sligochi (2022). BB(16) > Graham's Number. ''(EB/OL)''. https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>

	对于一些较大的 n，Wythagoras 证明了<math>BB(38)>f_{\omega\times2}(67)</math>、<math>BB(64)>f_{\omega^2}(4098)</math> 以及<math>BB(85)>f_{\varepsilon_0}(1907)</math>。		对于一些较大的 n，Wythagoras 证明了<math>BB(38)>f_{\omega\times2}(67)</math>、<math>BB(64)>f_{\omega^2}(4098)</math> 以及<math>BB(85)>f_{\varepsilon_0}(1907)</math>。

	Rohan Ridenour 证明了 BB(1015) 超过了 [[Loader数\|Loader 数]]<ref>https://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe</ref>。HypCos 在他的作品《大数入门》中提到 BB(160) 已经大于 Loader 数，但没有给出出处。		Rohan Ridenour 证明了 BB(1015) 超过了 [[Loader数\|Loader 数]]<ref>Cats Are Fully. Metamath turing machines. ''(EB/OL), Github''. https://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe</ref>。HypCos 在他的作品《大数入门》中提到 BB(160) 已经大于 Loader 数，但没有给出出处。

	据信 <math>BB(150)>f_{SHO}(10\uparrow\uparrow15)</math>，其中 [[SHO]] 是 [[Bashicu矩阵\|BMS]] 的极限。<ref>https://morphett.info/turing/turing.html?c95a199c8e8a3dd56452f8b7e28fabbf</ref>		据信 <math>BB(150)>f_{SHO}(10\uparrow\uparrow15)</math>，其中 [[SHO]] 是 [[Bashicu矩阵\|BMS]] 的极限。<ref>Morphett. Turing machine simulator. ''(EB/OL)''. https://morphett.info/turing/turing.html?c95a199c8e8a3dd56452f8b7e28fabbf</ref>

	== 相关函数 ==		== 相关函数 ==
第197行：		第197行：

	== 传言 ==		== 传言 ==
	有一些资料声称哥德巴赫猜想已经被证明最大反例一定小于 BB(27)，这实际上是错误的。正确的说法是，我们找到了一个 27 状态的 2 色图灵机<ref>~~https://link~~.~~zhihu~~.~~com~~/~~?target=~~https~~%3A~~//gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6</ref>，它停机当且仅当哥德巴赫猜想不成立。类似的，还存在一个验证黎曼猜想的图灵机，有 5372 个状态。这两个图灵机其实是告诉我们世界上存在有限时间内可以证明哥德巴赫猜想和黎曼猜想的程序，它们至少保证了哥德巴赫猜想和黎曼猜想是可被证明的，而不会是那种“不可证明”的命题。		有一些资料声称哥德巴赫猜想已经被证明最大反例一定小于 BB(27)，这实际上是错误的。正确的说法是，我们找到了一个 27 状态的 2 色图灵机<ref>Anonymous. list27.txt. ''(EB/OL), Github''. https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6</ref>，它停机当且仅当哥德巴赫猜想不成立。类似的，还存在一个验证黎曼猜想的图灵机，有 5372 个状态。这两个图灵机其实是告诉我们世界上存在有限时间内可以证明哥德巴赫猜想和黎曼猜想的程序，它们至少保证了哥德巴赫猜想和黎曼猜想是可被证明的，而不会是那种“不可证明”的命题。

	Yedidia 还写了这样一个程序，它验证这样一个命题: [[ZFC公理体系\|ZF]] 是[[一致性\|一致]]（自洽）的，它有 7918 个状态。		Yedidia 还写了这样一个程序，它验证这样一个命题: [[ZFC公理体系\|ZF]] 是[[一致性\|一致]]（自洽）的，它有 7918 个状态。

2025年7月29日 (二) 11:04 Tabelog

2025-07-29T11:04:35Z

←上一版本		2025年7月29日 (二) 19:04的版本
第14行：		第14行：
	我们可以引入一个表格来表示图灵机的程序。我们用列表示图灵机的当前状态，行表示读头对应的格子的值。每个指令都是一个有三个字符组成的字符串。第一个字符是读头把当前格子的值改变为什么值，第二个字符是读头接下来是向左移动还是向右移动，第三个字符是读头接下来把图灵机改变为哪个新的状态。		我们可以引入一个表格来表示图灵机的程序。我们用列表示图灵机的当前状态，行表示读头对应的格子的值。每个指令都是一个有三个字符组成的字符串。第一个字符是读头把当前格子的值改变为什么值，第二个字符是读头接下来是向左移动还是向右移动，第三个字符是读头接下来把图灵机改变为哪个新的状态。

	~~作为一个例子，我们给出一个图灵机的程序，它纸带上的取值是0或者1，它有两个状态A和B。~~		作为一个例子，我们给出一个图灵机的程序，它纸带上的取值是 0 或者 1，它有两个状态 A 和 B。

	[[文件:Busy-beaver-two-states-test.gif\|frame\|right\|200px\|二状态图灵机]]		[[文件:Busy-beaver-two-states-test.gif\|frame\|right\|200px\|二状态图灵机]]
第32行：		第32行：
	\|}		\|}

	例如，左上角的 1RB 代表当这个图灵机在状态A之下读取到了格子上是 0，那么它把格子的值改写为 1，向右移动一格，并且把图灵机的状态变为B。其余指令的含义是类似的，这里不再赘述。下面我们在一个所有格子全为0的纸带上运行这个图灵机，它的初始状态是A：		例如，左上角的 1RB 代表当这个图灵机在状态A之下读取到了格子上是 0，那么它把格子的值改写为 1，向右移动一格，并且把图灵机的状态变为B。其余指令的含义是类似的，这里不再赘述。下面我们在一个所有格子全为 0 的纸带上运行这个图灵机，它的初始状态是 A：

	000<u>0</u>00 A→0001<u>0</u>0 B→000<u>1</u>10 A→00<u>0</u>110 B→0<u>0</u>1110 A→01<u>1</u>110 B→011<u>1</u>10 B		000<u>0</u>00 A→0001<u>0</u>0 B→000<u>1</u>10 A→00<u>0</u>110 B→0<u>0</u>1110 A→01<u>1</u>110 B→011<u>1</u>10 B
第49行：		第49行：
	我们定义忙碌海狸函数如下：		我们定义忙碌海狸函数如下：

	一个能够停机的 2 色，n 状态图灵机，从全 0 的纸带开始，所能够扫过的最大格子数定义为 <math>BB(n)</math> 或者 <math>\Sigma(n)</math>。<ref>Rado, T. "[https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x On Non-Computable Functions.]" Bell System Technical J. 41, 877-884~~, May 1962~~.</ref>我们称这样的图灵机是“忙碌的海狸”。		一个能够停机的 2 色，n 状态图灵机，从全 0 的纸带开始，所能够扫过的最大格子数定义为 <math>BB(n)</math> 或者 <math>\Sigma(n)</math>。<ref>Rado, T (1962). [https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x On Non-Computable Functions]. ''Bell System Technical J''. 41, 877-884.</ref>我们称这样的图灵机是“忙碌的海狸”。

	=== 取值 ===		=== 取值 ===
第91行：		第91行：
	\|}		\|}

	可得 BB(2)=4。		可得 BB(2) = 4。

	[[文件:Busy-beaver-three-states-new.png\|frame\|right\|200px\|三状态图灵机]]		[[文件:Busy-beaver-three-states-new.png\|frame\|right\|200px\|三状态图灵机]]
第114行：		第114行：
	\|}		\|}

	可得 BB(3)=6。		可得 BB(3) = 6。

	[[文件:Busy-beaver-four-states-new.png\|frame\|right\|200px\|四状态图灵机]]		[[文件:Busy-beaver-four-states-new.png\|frame\|right\|200px\|四状态图灵机]]
第140行：		第140行：
	\|}		\|}

	可得 BB(4)=13。		可得 BB(4) = 13。

	BB(5) 所对应的图灵机是<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990, for Sigma(5).</ref><ref>[July 2nd 2024] [https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 We have proved "BB(5) = 47,176,870"] - News - The Busy Beaver Challenge</ref>		BB(5) 所对应的图灵机是<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990, for Sigma(5).</ref><ref>[July 2nd 2024] [https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 We have proved "BB(5) = 47,176,870"] - News - The Busy Beaver Challenge</ref>
第166行：		第166行：
	\|}		\|}

	可得 BB(5)=4098。		可得 BB(5) = 4098。

	对于更之后的 BB 函数，我们还未计算出精确值。我们有		对于更之后的 BB 函数，我们还未计算出精确值。我们有
第176行：		第176行：
	Milton Green 证明了<math>BB(2n)\gg 3\uparrow^{n-2}3</math>。<ref>Green, Milton. [https://doi.ieeecomputersociety.org/10.1109/SWCT.1964.3 A lower bound RADO's sigma function for binary turing machines]. Retrieved 2013-05-07.</ref>BB(6) 已经远远大于 27，因此这个下界是很弱的。		Milton Green 证明了<math>BB(2n)\gg 3\uparrow^{n-2}3</math>。<ref>Green, Milton. [https://doi.ieeecomputersociety.org/10.1109/SWCT.1964.3 A lower bound RADO's sigma function for binary turing machines]. Retrieved 2013-05-07.</ref>BB(6) 已经远远大于 27，因此这个下界是很弱的。

	[[葛立恒数]]是一个非常著名的大数，但它在一些较小的 n 就被 BB(n) 超越。目前最新的成果是 Daniel Nagaj 证明了 BB(14)>~~葛立恒数，该证明被~~ Shawn Ligocki 所确认。<ref>[https://www.sligocki.com/2022/07/11/bb-16-graham.html BB(16) > Graham's Number]</ref>		[[葛立恒数]]是一个非常著名的大数，但它在一些较小的 n 就被 BB(n) 超越。目前最新的成果是 Daniel Nagaj 证明了 BB(14)>G，该证明被 Shawn Ligocki 所确认。<ref>[https://www.sligocki.com/2022/07/11/bb-16-graham.html BB(16) > Graham's Number]</ref>

	对于一些较大的 n，Wythagoras 证明了<math>BB(38)>f_{\omega\times2}(67)</math>、<math>BB(64)>f_{\omega^2}(4098)</math> 以及<math>BB(85)>f_{\varepsilon_0}(1907)</math>。		对于一些较大的 n，Wythagoras 证明了<math>BB(38)>f_{\omega\times2}(67)</math>、<math>BB(64)>f_{\omega^2}(4098)</math> 以及<math>BB(85)>f_{\varepsilon_0}(1907)</math>。
第199行：		第199行：
	有一些资料声称哥德巴赫猜想已经被证明最大反例一定小于 BB(27)，这实际上是错误的。正确的说法是，我们找到了一个 27 状态的 2 色图灵机<ref>https://link.zhihu.com/?target=https%3A//gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6</ref>，它停机当且仅当哥德巴赫猜想不成立。类似的，还存在一个验证黎曼猜想的图灵机，有 5372 个状态。这两个图灵机其实是告诉我们世界上存在有限时间内可以证明哥德巴赫猜想和黎曼猜想的程序，它们至少保证了哥德巴赫猜想和黎曼猜想是可被证明的，而不会是那种“不可证明”的命题。		有一些资料声称哥德巴赫猜想已经被证明最大反例一定小于 BB(27)，这实际上是错误的。正确的说法是，我们找到了一个 27 状态的 2 色图灵机<ref>https://link.zhihu.com/?target=https%3A//gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6</ref>，它停机当且仅当哥德巴赫猜想不成立。类似的，还存在一个验证黎曼猜想的图灵机，有 5372 个状态。这两个图灵机其实是告诉我们世界上存在有限时间内可以证明哥德巴赫猜想和黎曼猜想的程序，它们至少保证了哥德巴赫猜想和黎曼猜想是可被证明的，而不会是那种“不可证明”的命题。

	Yedidia 还写了这样一个程序，它验证这样一个命题: [[ZF]] 是[[一致性\|一致]]（自洽）的，它有 7918 个状态。		Yedidia 还写了这样一个程序，它验证这样一个命题: [[ZFC公理体系\|ZF]] 是[[一致性\|一致]]（自洽）的，它有 7918 个状态。

	== 趣事 ==		== 趣事 ==

2025年7月29日 (二) 08:12 Tabelog

2025-07-29T08:12:53Z

←上一版本		2025年7月29日 (二) 16:12的版本
第44行：		第44行：
	图灵机的结构是简单的，但事实上，图灵机的计算能力是非常强大的。为了让图灵机计算函数，我们可以对其进行适当的编码。例如，如果要求开始时的输入是 <math>n_1,\cdots,n_k</math>，则在纸带上分别用 <math>n_1+1</math> 个连续的 1，……，<math>n_k+1</math> 个连续的 1 表示它们，数与数之间用 0 隔开。待图灵机结束运行之后，纸带上1的个数即为图灵机的输出。		图灵机的结构是简单的，但事实上，图灵机的计算能力是非常强大的。为了让图灵机计算函数，我们可以对其进行适当的编码。例如，如果要求开始时的输入是 <math>n_1,\cdots,n_k</math>，则在纸带上分别用 <math>n_1+1</math> 个连续的 1，……，<math>n_k+1</math> 个连续的 1 表示它们，数与数之间用 0 隔开。待图灵机结束运行之后，纸带上1的个数即为图灵机的输出。

	如果一个函数可以用一个图灵机来实现，那么定义其为一个'''图灵可计算函数'''。我们有如下的定理：图灵可计算函数和[[递归函数]]等价。即，凡是递归函数，都可以被某个图灵机所实现。		如果一个函数可以用一个图灵机来实现，那么定义其为一个'''图灵可计算函数'''。我们有如下的定理：图灵可计算函数和[[CKO#递归函数\|递归函数]]等价。即，凡是递归函数，都可以被某个图灵机所实现。

	==== 忙碌海狸函数 ====		==== 忙碌海狸函数 ====

2025年7月29日 (二) 08:10 Tabelog

2025-07-29T08:10:50Z

←上一版本		2025年7月29日 (二) 16:10的版本
第1行：		第1行：
	'''忙碌海狸函数（Busy Beaver Function，又名 BB 函数或 Radó 的 Σ 函数）'''，是一个不可计算的快速增长函数。它是最著名的[[不可计算函数]]，也是专业数学中出现的有史以来增长最快的函数之一。		'''忙碌海狸函数（Busy Beaver Function，又名 BB 函数或 Radó 的 Σ 函数）'''，是一个不可计算的快速增长函数。它是最著名的[[CKO#不可计算函数\|不可计算函数]]，也是专业数学中出现的有史以来增长最快的函数之一。

	=== 定义 ===		=== 定义 ===

2025年7月24日 (四) 12:18 Tabelog

2025-07-24T12:18:09Z

显示更改

2025年7月21日 (一) 11:48 Tabelog

2025-07-21T11:48:11Z

←上一版本		2025年7月21日 (一) 19:48的版本
第18行：		第18行：
	[[文件:Busy-beaver-two-states-test.gif\|frame\|right\|200px\|二状态图灵机]]		[[文件:Busy-beaver-two-states-test.gif\|frame\|right\|200px\|二状态图灵机]]

	{\| class="wikitable ~~class="article-table~~" border="0" cellpadding="1" cellspacing="1""		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
	! scope="col" \|A		! scope="col" \|A
第78行：		第78行：
	BB(2) 所对应的图灵机为：<ref>Rado, On non-computable functions. The Bell System Technical Journal, vol. 41, no. 3, pp. 877-884, May 1962, for Sigma(1) and Sigma(2)</ref>		BB(2) 所对应的图灵机为：<ref>Rado, On non-computable functions. The Bell System Technical Journal, vol. 41, no. 3, pp. 877-884, May 1962, for Sigma(1) and Sigma(2)</ref>

	{\| class="wikitable ~~class="article-table~~" border="0" cellpadding="1" cellspacing="1""		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
	! scope="col" \|A		! scope="col" \|A
第98行：		第98行：
	BB(3)所对应的图灵机是<ref>Lin & Rado. Computer Studies of Turing Machine Problems. Journal for the Association of Computing Machinery, vol. 12, no. 2, pp. 196-212, April 1965, for Sigma(3)</ref>		BB(3)所对应的图灵机是<ref>Lin & Rado. Computer Studies of Turing Machine Problems. Journal for the Association of Computing Machinery, vol. 12, no. 2, pp. 196-212, April 1965, for Sigma(3)</ref>

	{\| class="wikitable ~~class="article-table~~" border="0" cellpadding="1" cellspacing="1""		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
	! scope="col" \|A		! scope="col" \|A
第121行：		第121行：
	BB(4)所对应的图灵机是<ref>A. H. Brady. Solution of the non-computable "Busy Beaver" game for k=4. Abstracts for ACM Computer Science Conference (Washington DC, 1975), p. 27, ACM, 1975, for Sigma(4).</ref>		BB(4)所对应的图灵机是<ref>A. H. Brady. Solution of the non-computable "Busy Beaver" game for k=4. Abstracts for ACM Computer Science Conference (Washington DC, 1975), p. 27, ACM, 1975, for Sigma(4).</ref>

	{\| class="wikitable ~~class="article-table~~" border="0" cellpadding="1" cellspacing="1""		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
	! scope="col" \|A		! scope="col" \|A
第144行：		第144行：

	BB(5)所对应的图灵机是<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990, for Sigma(5).</ref><ref>[July 2nd 2024] [https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 We have proved "BB(5) = 47,176,870"] - News - The Busy Beaver Challenge</ref>		BB(5)所对应的图灵机是<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990, for Sigma(5).</ref><ref>[July 2nd 2024] [https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 We have proved "BB(5) = 47,176,870"] - News - The Busy Beaver Challenge</ref>
	{\| class="wikitable ~~class="article-table~~" border="0" cellpadding="1" cellspacing="1""		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
	! scope="col" \|A		! scope="col" \|A

←上一版本		2025年7月21日 (一) 19:48的版本
第18行：		第18行：
	[[文件:Busy-beaver-two-states-test.gif\|frame\|right\|200px\|二状态图灵机]]		[[文件:Busy-beaver-two-states-test.gif\|frame\|right\|200px\|二状态图灵机]]

	{\| class="wikitable ~~class="article-table~~" border="0" cellpadding="1" cellspacing="1""		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
	! scope="col" \|A		! scope="col" \|A
第78行：		第78行：
	BB(2) 所对应的图灵机为：<ref>Rado, On non-computable functions. The Bell System Technical Journal, vol. 41, no. 3, pp. 877-884, May 1962, for Sigma(1) and Sigma(2)</ref>		BB(2) 所对应的图灵机为：<ref>Rado, On non-computable functions. The Bell System Technical Journal, vol. 41, no. 3, pp. 877-884, May 1962, for Sigma(1) and Sigma(2)</ref>

	{\| class="wikitable ~~class="article-table~~" border="0" cellpadding="1" cellspacing="1""		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
	! scope="col" \|A		! scope="col" \|A
第98行：		第98行：
	BB(3)所对应的图灵机是<ref>Lin & Rado. Computer Studies of Turing Machine Problems. Journal for the Association of Computing Machinery, vol. 12, no. 2, pp. 196-212, April 1965, for Sigma(3)</ref>		BB(3)所对应的图灵机是<ref>Lin & Rado. Computer Studies of Turing Machine Problems. Journal for the Association of Computing Machinery, vol. 12, no. 2, pp. 196-212, April 1965, for Sigma(3)</ref>

	{\| class="wikitable ~~class="article-table~~" border="0" cellpadding="1" cellspacing="1""		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
	! scope="col" \|A		! scope="col" \|A
第121行：		第121行：
	BB(4)所对应的图灵机是<ref>A. H. Brady. Solution of the non-computable "Busy Beaver" game for k=4. Abstracts for ACM Computer Science Conference (Washington DC, 1975), p. 27, ACM, 1975, for Sigma(4).</ref>		BB(4)所对应的图灵机是<ref>A. H. Brady. Solution of the non-computable "Busy Beaver" game for k=4. Abstracts for ACM Computer Science Conference (Washington DC, 1975), p. 27, ACM, 1975, for Sigma(4).</ref>

	{\| class="wikitable ~~class="article-table~~" border="0" cellpadding="1" cellspacing="1""		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
	! scope="col" \|A		! scope="col" \|A
第144行：		第144行：

	BB(5)所对应的图灵机是<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990, for Sigma(5).</ref><ref>[July 2nd 2024] [https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 We have proved "BB(5) = 47,176,870"] - News - The Busy Beaver Challenge</ref>		BB(5)所对应的图灵机是<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990, for Sigma(5).</ref><ref>[July 2nd 2024] [https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 We have proved "BB(5) = 47,176,870"] - News - The Busy Beaver Challenge</ref>
	{\| class="wikitable ~~class="article-table~~" border="0" cellpadding="1" cellspacing="1""		{\| class="wikitable" border="0" cellpadding="1" cellspacing="1"
	! scope="col" \|		! scope="col" \|
	! scope="col" \|A		! scope="col" \|A