忙碌的海狸 |
您所在的位置:网站首页 › 海狸百科 › 忙碌的海狸 |
此条目没有列出任何参考或来源。 (2020年7月23日)维基百科所有的内容都应该可供查证。请协助补充可靠来源以改善这篇条目。无法查证的内容可能会因为异议提出而移除。 在计算机科学中,忙碌的海狸(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》中提出的。 目录 1 无限旅馆的机器人 1.1 一个状态的机器人 1.2 两个状态的机器人 2 相关的函数 2.1 忙碌的海狸函数 2.2 方程值和下界 3 例子 4 相关词条 无限旅馆的机器人假设有一排无限房间的旅馆,每个房间里面都装了一盏灯和一个开关。最初,所有房间的灯都是关的(状态0)。一个机器人管家从其中某一个房间开始工作。进入房间后,它的行为只能是选择开灯或关灯,然后移到相邻的左边或者右边房间去。 这个机器人可以处于若干个预先设定的状态中。在不同的状态下,它会根据房间灯的开关情况,选择不同的行为和下一步的状态。 一个状态的机器人 在“工作”态下:如果房间灯是关的,开灯,移动到左边的房间并转换到“停止”态 如果房间灯是开的,关灯,移动到左边的房间并转换到“停止”态在“停止”态下(这个游戏必须有一个停止态,不计算在机器人状态中):机器人停止,游戏结束。游戏开始后,这个“工作”态机器人进入某个房间后,开一盏灯,然后移到左边的房间并转换到“停止”态,游戏结束。我们可以验证,无论你如何设计机器人的行为(64种可能),在只有一种状态的约束下,机器人最多只能打开一盏灯,所以 Σ ( 1 ) = 1 {\displaystyle \Sigma (1)=1} 。 两个状态的机器人 在“惊恐”态下:如果房间灯是关的,开灯并移动到左边的房间去 如果房间灯是开的,恢复到“正常”态在“正常”态下:如果房间灯是开的,关灯并移动到左边的房间去 其余情况,转变到“惊恐”态在“停止”态下(这个游戏必须有一个停止态,不计算在两种状态中):机器人停止,游戏结束。对于以上两种状态的机器人,如果它初始态是“惊恐”,从它进入某一个房间开放,它便会打开房间的灯然后移到左边的房间。然后继续开灯,向左移,无限循环下去。这样的状态设定是不符合忙碌的海狸必须可以终止的条件。同理,如果它的初始态是“正常”,它也会无限向左移,并不属于忙碌的海狸。 下面我们看另外一种两个状态的机器人。 在“1”态下:如果房间灯是关的,开灯,移动到右边的房间,并转变到“2”态 如果房间灯是开的,保持,移动到左边的房间,并转变到“2”态在“2”态下:如果房间灯是关的,开灯,移动到左边的房间,并转变到“1”态 如果房间灯是开的,保持,移动到左边的房间,并转变到“H”态在“H”态下:机器人停止,游戏结束。这样的状态“1”机器人,从某个房间开始,可以进行6次移动,最终打开四盏灯(左边2个房间,开始的房间,和右边的一个房间),回到最左边的房间并停止游戏。2个状态的机器人,全部有 ( 2 × 2 × 3 ) 2 × 2 = 20736 {\displaystyle (2\times 2\times 3)^{2\times 2}=20736} 种行为设计,其实最多开灯的设计是4盏,所以 Σ ( 2 ) = 4 {\displaystyle \Sigma (2)=4} 。 3个状态的机器人,可以通过14次移动,最多打开6盏灯 Σ ( 3 ) = 6 {\displaystyle \Sigma (3)=6} 。 4个状态的机器人,可以通过107次移动,最多打开13盏灯, Σ ( 4 ) = 13 {\displaystyle \Sigma (4)=13} 。 4个更多状态的机器人,目前还不能计算出忙碌的海狸的函数值,比如目前我们猜测 Σ ( 5 ) ⩾ 4098 {\displaystyle \Sigma (5)\geqslant 4098} ,但还不能确认。 相关的函数 忙碌的海狸函数忙碌的海狸函数,又称为BB函数,或者Radó Sigma函数,记做 Σ ( n ) {\displaystyle \Sigma (n)} 或者BB(n),是n个状态的忙碌的海狸图灵机的最大输出。这一个增长特别快的函数,是一个非常著名的不可计算函数。Radó证明了这个函数最终会超过全部的可计算函数。 Σ ( n ) {\displaystyle \Sigma (n)} 还可以定义为集合 T = { n 1 , n 2 , ⋯ , n k } {\displaystyle T=\{n_{1},n_{2},\cdots ,n_{k}\}} 中最大的数,这个集合包括了n个状态的2色图灵机全部的输出。集合 T {\displaystyle T} 的大小不超过 ( 4 n + 4 ) 2 n {\displaystyle (4n+4)^{2n}} (这是n个状态的全部图灵机数量)。 更普遍的, Σ ( n , m ) {\displaystyle \Sigma (n,m)} 表示n个状态,m个颜色的忙碌的海狸图灵机。 方程值和下界 Values of S(n, m) nm 2-state 3-state 4-state 5-state 6-state 7-state 2-symbol 6 21 107 7007471768700000000♠47176870? > 9000000000000000000♠7.4×1036534 > 102*1010107007187053530000000♠187053533-symbol 38 ≥ 7017119112334170342♠119112334170342540 > 9000000000000000000♠1.0×1014072 ??? ??? ??? 4-symbol ≥ 7006393296400000000♠3932964 > 9000000000000000000♠5.2×1013036 ??? ??? ??? ??? 5-symbol > 9000000000000000000♠1.9×10704 ??? ??? ??? ??? ??? 6-symbol > 9000000000000000000♠2.4×109866 ??? ??? ??? ??? ??? Values of Σ(n, m) nm 2-state 3-state 4-state 5-state 6-state 7-state 2-symbol 4 6 13 7003409800000000000♠4098? > 9000000000000000000♠3.5×1018267 > 101010107007187053530000000♠187053533-symbol 9 ≥ 7008374676383000000♠374676383 > 9000000000000000000♠1.3×107036 ??? ??? ??? 4-symbol ≥ 7003205000000000000♠2050 > 9000000000000000000♠3.7×106518 ??? ??? ??? ??? 5-symbol > 9000000000000000000♠1.7×10352 ??? ??? ??? ??? ??? 6-symbol > 9000000000000000000♠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 1LD 1RE 1LA 1LH 1 1LE 1RF 0RB 0LC 0RD 1RC结果: ≈3.515 × 1018267 个"1" ≈7.412 × 1036534 步。 相关词条 拉约数 葛立恒数 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |