2006-11-24 変な関数 数学 n状態0/1のチューリングマシンを考える。 このチューリングマシンに全て0が書き込まれたテープを与えたとき、 1をできるだけたくさん書き出すプログラムを考える。 ただし、このプログラムは停止するものだけを考える。 このとき、チューリングマシンが停止するまでに出力した1の数をΣ(n)と定める。さて、Σ(1)=1、Σ(2)=4、Σ(3)=6、Σ(4)=107である。Σ(5)はいくつだろうか?