ビジービーバー関数（Busy beaver）について、中高生でもわかる

質問

ビジービーバー関数（Busy beaver）について、中高生でもわかるわかりやすい説明をどなたかお願いします。
ウィキペディアの説明を読み理解しようとしてみましたが、どうもよくわかりません。
関連ないかもしれませんがグラハム数がなんとなく分かったというレベルです。

回答No.2

20080715

＞最初の段階、遷移関数という言葉でまずつまずいてしまいます。
＞ ……
＞も私には想定されている状況が、想像できないのです。

なるほど。eheiさんは計算理論を学習した経験は皆無なのですね。
いきなりチューリングマシンを理解しようとするのではなく、
まずは有限オートマトンから勉強されてはいかがですかね。
ここに良さそうなサイトがあります。
http://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/InfoMath/2005/index.html

チューリングマシンについての説明：
http://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/InfoMath/2005/note/5/Slide02.html

初心者にもわかりやすく書かれてある計算理論の本として、
次のものをあげておきます。
「計算理論の基礎　マイケル シプサ著」(共立出版)

お礼

残念ながらご紹介いただいたサイトでは、私には難しく理解することができませんでした。
どうもご回答ありがとうございました。

回答No.1

20080715

＞ウィキペディアの説明を読み理解しようとしてみましたが、
＞どうもよくわかりません。

ウィキペディアの説明というのは、これのことですか？
http://ja.wikipedia.org/wiki/%E3%83%93%E3%82%B8%E3%83%BC%E3%83%93%E3%83%BC%E3%83%90%E3%83%BC

この説明は丁寧に書かれてあると私は思うのですが、eheiさんはこの説明の
どのへんがよくわからないのですか？
具体的にわからないところを言ってみてください。

＞中高生でもわかるわかりやすい説明をどなたかお願いします。

チューリングマシンについての少しの知識があれば、
ビジービーバー関数についてのウィキペディアの説明は
中高生でも理解できるとおもいます。

参考URL：

http://ja.wikipedia.org/wiki/%E3%83%93%E3%82%B8%E3%83%BC%E3%83%93%E3%83%BC%E3%83%90%E3%83%BC

補足

それでは、小学生でも解かる説明をお願いします。と言い換えさせてもらいます。

全体にわたって解からないので、具体的に絞れないのですが、
最初の段階、遷移関数という言葉でまずつまずいてしまいます。
その後の、
1. マシンの現状態
2. 現在の位置におけるテープ上の記号
そして三つの出力を持つ。

1. テープの現在位置から読み出された記号を上書きするための記号（たまたま入力と同じ記号になる場合もある）
2. テープ上を移動すべき方向（「左」または「右」）
3. 遷移先の状態（たまたま現状態と同じ状態になる場合はあるし、または「停止」状態を指す可能性もある）

も私には想定されている状況が、想像できないのです。