ビジービーバー
ティボール・ラドーは、1962年の論文で以下のように「ビジービーバー・ゲーム」を導入した。
記号 {0, 1} と n 個の動作状態(それぞれ 1, 2, ..., n で表すか、または A, B, C ...などと書く)を持つチューリングマシンを考える。なお、動作状態にはもう一つ「停止」状態もあるとする。
彼が定義したチューリングマシンは次の通りである。
2つの方向に動作可能な無限長(または端のない)テープの上で動作する。
このマシンには「遷移関数」があり、次の2つの入力を取る。 マシンの現状態 現在の位置におけるテープ上の記号
そして3つの出力を持つ。 テープの現在位置から読み出された記号を上書きするための記号(たまたま入力と同じ記号になる場合もある) テープ上を移動すべき方向(「左」または「右」) 遷移した後の状態(たまたま現状態と同じ状態になる場合はあるし、または「停止」状態を指す可能性もある)
以上より、このチューリングマシンは、その「プログラム」を次のような5つのタプル(組)の情報を有限個並べた表として書けるようなマシンである。
(現状態、現記号、次に書くべき記号、移動方向、次状態)
このマシンは「停止」状態に達したときに停止する。
空のテープ(ここでは全てのセルに 0 が書かれたテープを「空テープ」と呼ぶ)をセットして処理を始める。マシンを走らせて(遷移関数を繰り返し起動する)、マシンがいずれ停止したならば、テープに書かれた 1 の数を数える。
n-状態ビジービーバー(BB-n と書く)ゲームは、停止するまでにテープに 1 を最も多く出力するような n-状態チューリングマシンを見つけ出す、というゲームである。
ラドーは次のように書いている。
結果: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107ステップ、合計13個の "1")