# 忙碌的海狸

> 在计算机科学中，忙碌的海狸（Busy Beaver）是一个在给定参数后，寻找可能产生的最大输出的可终止程序。忙碌的海狸游戏包括设计一个可终止的，只输出0或1的图灵机，让其在一条纸带上尽可能多的输出1.。包含两个状态的忙碌的海狸游戏有下面两条规则：。该图灵机包括除终止态以外的两个状态。纸带初始值都是0。玩家需要设计出可能输出最多1的状态转换表格，同时也要确保图灵机是会终止的。

- ID: m00181
- 分类: system
- 领域: 系统论

## 定义

在给定状态数量（如5个状态）下，能运行步数最多但在最终必须停机（不能死循环）的程序。其步数增长速度快得超乎想象（非可计算函数）。脚手架作用： 探索优化的极限。它提醒我们，在有限的规则和资源（状态）下，系统的潜在复杂度和产出能力是超乎直觉的。不要轻易认为“这点资源做不出什么花样”，你可能只是没找到那个“忙碌海狸”的配置。

## 机制

Busy Beaver 问题：在给定状态数的图灵机中，求能写下最多 1（或最多步数）后停机的机器，其函数增长超越任何可计算函数，用以揭示可计算性边界与停机问题的不可解。

## 练习

1）固定状态数 n；2）枚举所有 n 态图灵机；3）记录其中停机者的最大产出/步数；4）认识到对更大 n 该值不可计算、不可判定。

## 脚手架用法

探索优化的极限。它提醒我们，在有限的规则和资源（状态）下，系统的潜在复杂度和产出能力是超乎直觉的。不要轻易认为“这点资源做不出什么花样”，你可能只是没找到那个“忙碌海狸”的配置。

[阅读网页](https://thinkingmodels.site/entries/detail/m00181)