計算モデル

手順による処理の記述では、コンピュータの命令を抽象化して、人間が「理解できる」変数やifなどの形式で形式でプログラムを表した。 しかし、より複雑な処理をするプログラムを記述する場合、変数やifなどの形式を組合わせただけでは、人間が理解することがどんどん難しくなってしまう。 そこで、処理の表現を更に抽象化した計算モデルがいろいろと考えられている。

• 計算モデル: コンピュータによる計算を抽象化したもの

• 計算モデルの例

  • 有限状態機械(有限状態オートマトン、有限オートマトン、オートマトン)
    • 現実のコンピュータよりも低い計算能力
    • あらかじめ動作の性質を分析しておくのが容易

  • チューリング機械・ランダムアクセス機械
    • 有限状態オートマトン+(無限に長いテープ or メモリ)
    • 現実のコンピュータと「同じ」計算能力
      (計算できるかできないかだけの観点で見たときに「同じ」という意味の「同じ」)

  • 帰納関数・ラムダ計算
    • 数学的な関数を抽象化したもの
      関数といっても侮ってはいけない。凄い関数も定義できる。
      例: アッカーマン関数

      ack(0,n) = n+1 ack(m,0) = ack(m-1,1) ack(m,n) = ack(m-1,ack(m,n-1))

      デモ用プログラム: ackermann.rb

    • 現実のコンピュータと「同じ」計算能力
      (計算できるかできないかだけの観点で見たときに「同じ」という意味の「同じ」)

yamaguch@mail.ecc.u-tokyo.ac.jp

Copyright 2011 Kazunori Yamaguchi 山口和紀@東京大学総合文化研究科