ビジービーバー
ビジービーバー（英：busy beaver）とは、計算可能性理論で扱われるある種のチューリングマシンである。この名称は「仕事人間」を意味する英語の慣用句に由来する。ビジービーバーは空のテープから処理を開始し、可能な限り走り続けるが、最終的には停止する。これは停止するチューリングマシンのクラスが消費し得る時間と領域（テープ）の長さの上限を与える。

ビジービーバー関数はこの上限を数値化するものであり、計算不能関数の一例でもある。この関数はいかなる計算可能関数よりも急速に増大するということを証明できる。ビジービーバー関数の概念は、ティボール・ラドーによる1962年の論文 "On Non-Computable Functions" の中で、「ビジービーバー・ゲーム」という名称で初めて導入された。
Q818930
計算可能性理論
Concept
Q163310
チューリングマシン
Concept
Q622849
停止
Concept
None
計算不能関数
UNK
None
ティボール・ラドー
UNK
Q2764
1962年
TIME
Q1427965
ビジービーバー
Concept
Q1427965
ビジービーバー
Concept
Q1427965
ビジービーバー
Concept
Q1427965
ビジービーバー
Concept
Q1427965
ビジービーバー
Concept
58-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1962年
DATE
instance of
instance of
instance of
instance of
instance of