ビジービーバー
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/07 05:45 UTC 版)
ビジービーバー（英：busy beaver）とは、計算可能性理論で扱われるある種のチューリングマシンである。この名称は「仕事人間」を意味する英語の慣用句に由来する。ビジービーバーは空のテープから処理を開始し、可能な限り走り続けるが、最終的には停止する。これは停止するチューリングマシンのクラスが消費し得る時間と領域（テープ）の長さの上限を与える。
- ^ 記号の個数を m とおけば、[2m(n+1)]mn。 チューリングマシンを表す状態遷移表（縦に記号、横に状態を並べる）において、1つのセルの取りうる値の候補が、左右の動きの候補が2個、出力する記号の候補がm個、停止を含んだ遷移先の状態の候補がn+1個なので、[2m(n+1)]mnになる
- ^ 訳注：Turing-instructions：チューリングマシンのプログラム。ここで言う「状態」は、テープから読み取った記号ごとに対応する動作指示を記述する形を採るので、すなわちプログラムでもある。#ビジービーバーであるチューリングマシンの例を参照
- ^ 訳注：ここで言うシフトとはテープ上を移動する操作のことか？
- ^ Adam Yedidia and Scott Aaronson (May 2016). A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory (Technical Report). MIT. arXiv:1605.04343. Bibcode:2016arXiv160504343Y。
- ^ a b “The Busy Beaver Frontier”. 2023年9月29日閲覧。
- ^ a b “The Undecidability of BB(748)”. 2023年9月29日閲覧。
- ^ “Three announcements”. Shtetl-Optimized blog. (2016年5月3日) 2023年9月29日閲覧。
- ^ “GitHub - sorear/metamath-turing-machines: Metamath proof enumerators and other things.”. GitHub (2016年5月16日). 2023年9月29日閲覧。
- ^ “GitHub - sorear/metamath-turing-machines: Metamath proof enumerators and other things.”. GitHub (2017年8月8日). 2023年9月29日閲覧。
- ^ “Life, blogging, and the Busy Beaver function go on” (2023年7月5日). 2023年9月29日閲覧。
- ^ グレゴリー・チャイティン、1987年
- ^ “The nineteenth Busy Beaver number is greater than Graham's Number!” (英語). Googology Wiki. 2023年1月3日閲覧。
- ^ 訳注：例えば現状態がAで入力が記号0なら、0行A列が交差する位置のマス目の中身を実行する
- ^ 訳注：Rはright(右) Lはleft(左) Hはhalt(停止)を示す
[続きの解説]
「ビジービーバー」の続きの解説一覧
- ビジービーバーのページへのリンク
