7/5 演習[オートマトンシミュレータ]
補足
- はしかに感染して欠席する(した)人は，課題の提出等に関して考慮するので，事後に申し出るように．
- 講義で使ったスライドはcfive「情報」教材に順次アップロードしていく予定である．講義独自の試験問題は，講義のWWWページと講義スライドの範囲から出る．
- 昨年度の共通問題は，情報のページで公開されているので参考にするように．
- 2006年度独自問題
質問への答え
- Q.
- 「∵」という記号の出し方が分かりません．
- A.
- その場では答えられなかったので調べてみました．MacOSの仮名漢字変換システム「ことえり」では「きごう」で変換を繰り返すと出てくるようです．ただ，「きごう」を変換して出てくる記号の中には機種依存文字(MacOS以外で読むと化ける可能性があるもの)もあるので(ことえりでは変換の際にマークが付きます)，注意してください．
- Q.
- 教科書の6.3.2の「チューリング機械の停止問題」の証明が読んでも理解で
きない
- A.
- 6.3.2は試験の範囲外なので講義では触れませんでしたが，たしかに教科
書を読むだけでは理解するのは難しいでしょうね．ここの意味を実感するには，
- P. 139から始まるチューリング機械の動作を理解し，実際にいくつかの意味を持つチューリング機械を作ってみる．また，チューリング機械の停止性に関して経験を積む．
- 多テープチューリング機械などいくつかの拡張に関して，能力的に等価であることを証明する．
- 万能チューリング機械を構成してみる．
位の準備が必要です．ここまできちんとやると時間がかかるので，多くの場合は，
- 適当なプログラミング言語L(プログラムをデータとして扱いやすいものが向いている．Lispなどを例として使うことが多い)が万能チューリング機械と計算能力が等価であることを仮定する．
- 6.3.2の証明の「チューリング機械」を「Lで書かれたプログラム」と読み
替える．
とやって教える場合が多いようです．この場合も「適当なプログラミング言語」をマスターしていることが条件になります．
- Q.
-
プログラム４に関して
16ビットの限界数は６５５３６個であるがこのプログラムシミュレーターでは
プラスとマイナス分けていたため正の最大値Mは40000＞M、よってこのままでは
８！＝４０３２０
が表せないことになる。
しかし実際に計算させてみると
８！＝−25216という値を得た。これに６５５３６を加えると４０３２０となりシミュレーターはプラスの上限を超
えたものをマイナスにかえることで計算を実行していたことがわかる。
- A.
- よく気がつきましたね．実際のCPUでも整数の演算結果が表現できる範囲の数を超えている場合に
エラーなどを起こさずに間違った(ただし法則にしたがった間違え方の)値を返すことが多いので，
シミュレータもそのようになっているようです．
今日の演習