比較プログラム言語論平成１６年５月２６日森田彦レポート（5/19）総括＜テーマ＞  本日の講義で、あなたが最も興味を持った点はどのような点ですか？講義の全体的な感想と共に、できる限り具体的に、200字～400 字程度で記述して下さい。＜興味を持った点＞    チューリング機械オートマトン理論形式文法とオートマトンの関係チューリング機械  今日の講義で一番興味が持てたのは、１９３７年にイギリスの数学者である。アラン・チューリングが計算理論のモデルとして提唱したチューリング機械です。なぜなら、単純な原理だが、一定の手順に従えば答えが求められるような計算は、理論上すべてチューリング機械で実行できるとされている。チューリング機械そのものは理論だけの存在であり、実際に製作されたわけではないが、現  在のコンピュータも突き詰めればチューリング機械の原理に従っていると言える。今日の講義で興味を持ったところは、まず、数学の世界における計算は四則演算だけでなく、物事の問題を解決まで導ける一定のプロセスも計算とされているということだというところです。さらに、それを踏まえたうえでのチューリングの考えです。「計算とは紙に書かれた記号を読み、それに基本的な思考操作を加えて新しい記号を書くことの繰り返し」と言われて、数学世界の計算の定義を初めて知り、漠然として、把握できなかった状態から一気に救われた気がしました。チューリングの考え    解ける、解けない、つまり計算できる、できない、とはどのように定式化できるのだろう？計算できるとはどういうことか？計算過程をどのように表現できるか？→どこまで単純化して（しかもエッセンスを失わずに）表せるか？→ モデル化最終的にたどりついたのが、チューリング機械テープヘッド制御部計算（思考）過程を簡単な機械で表現したところがポイント！オートマトン   オートマトンとは受理判定機械の事であり入力に際しそこに記載された語を読み、それが言語に属するかを判断する機械、入力されたものがある基準を満たしているかどうかと言う判断をする機械、と理解することが出来た。このオートマトンには四種類のグループ分けがあるということでした。これらと、今まで学習してきた内容から言語にはそれぞれ系統があり、やはり用途はそれぞれに向き不向きがあるものなのだと思いました。今日の授業では有限オートマトンの話が一番おもしろかったです。チューリングマシンでは制限なく、全てを受け入れてしまうようですが、それでは大変だと思います。有限オートマシンは有限だし、定義によって受理される、されないの制限もあるのでやはりこちらのほうが、精度が高いのではないかと思います。有限オートマトン Σ テープヘッド有限状態装置 Q テープ、ヘッド、有限状態装置から構成ヘッドは一方向のみ動く  有限オートマトンＭの定義 M=(Q,Σ,δ,q０,F) Q:状態、Σ：入力記号、δ：状態遷移関数 q0：初期状態、F：受理状態  有限オートマトンの例テープ a b ヘッド有限状態装置 q0 Q={q0,q1,q2}、Σ={a,b}、F={q2} δ(q0,a)=q1, δ(q0,b)=q0 , δ(q1,a)=q1, δ(q1,b)=q2 , 読み取るだけ！ δ(q2,a)=q1, δ(q2,b)=q0  入力記号“ab”が受理されるか？ δ(q0,ab)= δ(δ(q0,a),b)=δ(q1,b)=q2 受理！  入力記号”ba”は受理されるか？ δ(q0,ba)= δ(δ(q0,b),a)=δ(q0,a)=q1 受理されない！  オートマトンの考え      人間の思考過程→（脳の）状態の変化状態を記号で表現すれば→記号の変化規則を状態遷移関数で表現できる。状態遷移関数で、“思考”を数学的に表現できる。言語は、“思考”の一例２進数で状態を表現すれば→コンピュータで問題を解ける。→計算可能な問題はコンピュータで全て処理可能→初期のコンピュータ科学者の夢オートマトンと形式文法の関係   今日の講義で興味を持ったのは、数学の分野で考えられた「オートマトン」という理論と、言語の分野で考えられた「形式文法理論」が対応したということです。もちろん、対応させるまでにはいろいろな研究があったと思いますが、別の分野で別のことを考えていたものが、同じような法則？のもとで対応したというのは面白いなと思いました。小出先生の地学の講義で「数学と物理学の一部は言葉の通じない宇宙人にでも伝えることが出来る『宇宙語』である」といっていたのですが、そうすると数学は「世の中のものを数や式を使って一般的（宇宙的？）に表すことはできないか」というものになると思います。そう考えれば言葉のならびや規則性が数学的な式で表されたとしても不思議ではありませんが、世間的に見れば対極にあるものがうまく融合したというのはとても不思議なことだと思います。私が本日の講義で興味を持った点は、数学的に考えられた「オートマトン」という理論と言語の分野で考えられた「形式言語理論」と関係性です。例えば、文脈依存文法言語と線形有界オートマトンが関係性を持っているようにその他にも関係性を持つものがいくつかあって、数学的に考えられた「オートマトン」と言語の理論で考えられた「形式言語理論」が対応しあうという点に興味を持ちました。質問１  現在はコンピュータの進歩により、プログラムが遠回りで複雑に作られても、性能の部分でそれを補っているということです。たしかに私達が使っているパソコンでも、余程難解で複雑でもないかぎり、数秒～数時間の単位でコンパイルできます。また、そのことからプログラムのソフト的進歩より、コンピュータのハード的進歩の方が早いといえます。そこで質問ですが、プログラムの進歩はどのくらいの、ペースで起こっているのでしょうか。例えば、パソコンなら（CPU？）ムーアの法則なるものがあったような気がします。プログラムに関してそういったものは無いのでしょうか。ムーアの法則    半導体メーカーIntel社の創設者の一人であるムーア博士が提唱した経験則（１９６５年）半導体の集積密度は18～24ヶ月で倍増する。現在では、集積密度を性能に置き換えて理解されている。→今でも性能向上の目安を与えてくれている。ソフトウェアに関しては・・・？開発効率に関して対応する法則はない。ただ、幾つかの（大きな）発展の契機はある。高水準プロミング言語の登場 → 構造化プログラミング → オブジェクト指向プログラミング質問２テープヘッド制御部    チューリング機械の動作で、「ヘッドが見えている記号を書き換える」というものがありましたが、その後の例で説明を聞いていたものの、なぜ記号を置き換えるのかがわからなかったです。チューリングマシンではなぜヘッドがどっちにでも動くようになっていたのですか？1方向じゃチューリングマシンはなりたたなかったのでしょうか？オートマンのヘッドの動きはわかりました、左右に動いて状態遷移関数を使うのはいいのですが、有限オートマンの一方方向だけに動くことの、一方方向の向きは決まっているのでしょうか？？レポートへのコメント    5/12の＜質問＞Ⅳ-2（エラーを自動的に修正してくれた方がよい!?）について感想と意見 5/12の「質問Ⅴ Brew」について質問への回答 5/12の「前回レポートへのコメントⅡ．Javaは重い!?（4/28＜質問＞の３）に対して」についてレポートを書いた当事者からの補足ホームページを参照して下さい。 Delphi VS Java 言語によって文法エラーのレベルが異なる。＜Delphi＞＜Java＞ var a,b,c: Integer; begin a:=4; b:=2; c:=a/b; ← エラー end; 文法的に厳しい int a,b,c; a=2; b=3; c=a/b; エラーなし！皆は、どちらを好みますか？ Delphi vs Java １＜Delphi＞個人的にDelphiとJavaを比べての私の好みですが、例だけを拝見すると、Delphiの方が、勝手が良い気がします。コンパイラが間違いを細かく指摘してくれれば見落としがちな小さな間違いが少なくなる気がします。＜Java＞自分もよくプラグラムを打ち間違えエラーを起こしています。どこが間違っているか分かれば非常に便利だと思いますが、便利なのは素人だけだと思います。プロからしてみればいちいちエラーが表示されるのは不便だと思われます。「どこが、どう、間違っているか」指摘される（訂正される）機能が優先か、個人（プログラマー）の能力の向上が（優先か）については、後者だと思います。個人的には楽なのはいいが、物に頼ってばかりなのはどうかと思います。 Delphi vs Java ２＜Delphi＞  私はDelphiの方が好ましいと思います。Javaは曖昧である分、長いプログラムでのエ＜Java＞に厳しいほうの言語がいい DelphiとJavaのエラーレベルの比較では私はJavaの方が好きです。なぜなら、動かせるのに、動かさずエラーを出すDelphiはちょっと融通が利かないように思えるからです。言語によってエラーのレベルが異なるという点についてはエラーがゆるい方がいいと思います。理由は間違った状態で実行すると動作の段階でどのようなエ間違っているところがすぐにわかるからいいと思った。ラーが出るのかを体験しておきたいからです。  ラーの特定が、非常に難しいと思えるからです。その点、始めから厳しく書いておく、 Delphiなら特定しやすいと  思えるからです。 DelphiとJavaの文法エラーのレベルが言語によって異なるということを知った。私は文法的と思いました。エラーがでれば  Delphi vs Java （現時点での整理） Delphi派、Java派が主張する（各々の）メリット＜Delphi＞＜Java＞文法的に厳しいので、エラーを未然に防ぐことができる。  これにより、エラーの特定がしやすくなる。  ＜もう一つの視点＞  記述の自由度が（相対的に）高いので書き方に融通が利く。  エラーを体験することで実践的な理解が深まる。エラー検出について  文法的に厳しくし、コンパイラのレベルで検出できるようにすべき。  文法あるいはコンパイラに頼るのではなく、プログラマーの技量を伸ばすべき！＜本日のテーマ＞次の２点について、皆の意見を述べてもらいます。 1. 2. 初めて学習するプログラミング言語としては、文法が厳密でエラーを未然に防ぐタイプのものが良いですか、それとも、記述の自由度が高く融通が利くタイプの方が良いと思いますか？プログラム開発の効率を上げるためには、次のどちらの要因を（より）重視しますか？ ① 言語の文法を厳しくし、文法エラーのチェックレベルを高めることで、エラー発生をできるだけ未然に防ぐようにする。 ② プログラム開発の手法をプログラマが身につけ、結果的にエラーを減らすようにする。第６回目レポート     前の２点について、あなたはどちらの意見ですか？あなたの意見と、そう考える理由をできる限り明確に説明して下さい。いずれも200字程度。なお、上の記述を行った上で,（いつも通り）講義の感想や質問等を付加しても結構です。提出先：[email protected] 件名：「学籍番号（半角）+半角空白＋氏名」を記入して下さい。例） s02xxx 学院太郎形式言語理論との関係言語の種類受理するオートマトン句構造文法言語チューリング機械文脈依存文法言語線形有界オートマトン文脈自由文法言語プッシュダウンオートマトン正規文法言語有限オートマトンコンパイラ（+コンピュータ）→オートマトンの一種数学による統一的理解の例（補足）ガリレオ・ガリレイの言葉自然は、数学という言語によって書かれている。  同時に彼は、当時の数学の限界も認識していた。  その数学とは・・・微積分学  ガリレオの死後、ニュートンによって完成される。  地上の運動と、天上の運動を（微積分学に基づく）力学として統一的に理解することに成功。  リンゴが木から落ちることと、月が地球を回る運動は同じ。