計算理論

岡本 吉央

前半を岡本が担当します．後半は垂井先生が担当します．

ショートカット： 講義資料 | コメント | 成績評価 | 公式シラバス | スケジュール | 参考書 |

講義資料

• 11/26 (8) 前半のまとめ
  • スライド (11/28修正) | 印刷用スライド (11/28修正) | 用語集
  • 講義動画
  • 前半のレポート課題は，下の方にあります．
• 11/19 (7) 再帰定理
  • スライド (11/21修正) | 印刷用スライド (11/21修正) | 演習問題 | 用語集
  • 講義動画
• 11/12 (6) 停止性問題
  • スライド (11/16修正) | 印刷用スライド (11/16修正) | 演習問題 | 用語集
  • 講義動画
• 11/5 (5) 計算可能性
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • 講義動画
  • 参考プログラム (Rubyプログラム)
    • 万能プログラム (細かいところが間違っているかもしれない)
• 10/29 (4) コード化
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • 講義動画
  • 参考プログラム (Rubyプログラム)
    • 対に関するプログラム | リストに関するプログラム
• 10/15 (3) チャーチ・チューリングの定立
  • スライド (10/19修正) | 印刷用スライド (10/19修正) | 演習問題 | 用語集
  • 講義動画
  • 演習問題3.7と3.10の提出期限は延期します．
• 10/8 (2) 計算モデル
  • スライド (10/9修正) | 印刷用スライド (10/9修正) | 演習問題 (10/12修正) | 用語集
  • 講義動画
  • 参考プログラム (WHILEプログラム風Rubyプログラム)
    • add | infloop | mult | isEven | half
• 10/1 (1) 計算とは何か？
  • スライド | 印刷用スライド | 演習問題 (10/12修正) | 用語集
  • 講義動画
  • 参考資料
    • Minecraftで論理回路を作る
    • Super Mario Makerで論理回路を作る

• 11/26 (8) 前半のまとめ
  • コメントをありがとうございました．次回からは垂井先生の担当となります．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました．
    -- こちらこそありがとうございました．
  • お疲れ様でした
    -- お疲れ様でした．
  • 休み明けの授業で疲れました、、
    -- お疲れ様でした．
  • 前半ありがとうございました
    -- こちらこそありがとうございました．
  • 前半の授業ありがとうございました
    -- こちらこそありがとうございました．
  • 特になし
    -- ありがとうございました．
  • 前半ありがとうございました
    -- こちらこそありがとうございました．
  • 前半の授業、ありがとうございました。
    -- こちらこそありがとうございました．
  • 前半の授業ありがとうございました．レポート頑張ります．
    -- こちらこそありがとうございます．レポートにはしっかりと取り組んで下さい．
  • レポート頑張ります
    -- レポートにはしっかりと取り組んで下さい．
  • 前半の授業、とても面白かったです！計算理論に増々興味を持つことができました！
    -- それはよかったです．ありがとうございました．
  • 今の数学では計算できない問題が多くあることを知って、これからまだ進化していく分野なのだと感じました。
    また、前半の授業について内容が難しく感じる部分は多かったですが、自分にとって全く新しい内容ばかりだったので面白かったです。
    -- 新しい内容をやらないと，授業をやっている意味がないので．
  • 8回分ありがとうございました。
    今日間違って後半の方に入ってしまったのですがURLが違ったようでエラー画面が出てきたので修正お願いします。おそらくpwdの直前の?が抜けてるんだと思います。
    -- ありがとうございます．ご指摘どおりです．修正しました．
  • 証明問題を解くときのコツが分からないです
    -- 「証明問題」というものがないと認識することだと思います．
    私はたまに入試の採点をすることがありますが，たいてい愕然とします (もう愕然とするのには慣れましたが)．なぜかというと，そこに書かれているものが式の羅列であり，それによって何を説明しようとしているのか，全く分からないからです．入試でなくても，期末試験であってもそういうことは起きます．そうすると，それを紐解こうとするだけで (もっと具体的に言えば，1つの等式を読み解くだけで)，3〜4時間費やすことがあります．そして，結局分からないことがあります．こんなことを100人分の答案に対していちいちやっていたら，時間が足りません．(ここまで，半分以上，愚痴を含みます．)
    つまり，皆さんは勝手に「計算問題」と「証明問題」という分類をしているかもしれませんが，計算問題であっても証明問題であっても，その答案というのは自分の考えを読み手に伝えるものなのだという認識をまず持ってほしいのです．説明をするということは文章を書くということです．答案は文章です．式の羅列だけで文章を成立させるのは非常に困難です．皆さんは「計算問題」に対しては，式を羅列するだけで答案を構成したつもりになっているので，計算問題はできている気になっているかもしれませんが，「証明問題」ではそうはいかないので，できていないということなのだと思います．そうなると，結局，皆さんが苦手なのは「証明問題を解く」ことなのではなくて「文章を書く」ことなのだと思います．
    もう一つ，この授業が『計算理論』だったのですから，その視点から述べると，「証明も計算」です．証明というのは人間が行なう知的活動であって，人間が行なう知的活動は計算である，という立場において，証明は計算であると見なせます．あるいは「カリー・ハワード対応」というものがあるので，それを調べてみるのもいいかもしれません．
  • 一見簡単そうに見える問題も証明するとなると難しいのだなと思った。
    -- そうかもしれませんね．その点は皆さんもしっかりと考えてみて下さい．
• 11/19 (7) 再帰定理
  • コメントをありがとうございました．
  • 特にありません。
    -- 了解しました．
  • あまりよく理解できなかった。
    -- どこが分からなかったのか，ということをまずは明確にしてみて下さい．そうすれば，何を調べればよいのかもわかると思いますし，解決に近づくと思います．
  • 先週コメント忘れてしまいました　すいません　レポートがんばります
    -- はい，よろしくお願いします．
  • ありがとうございました
    -- こちらこそありがとうございました．
  • ありがとうございました
    -- こちらこそありがとうございました．
  • 今日は暑いです。
    -- そうですね．今年の冬は暖かいのかもしれません．
  • 明日から調布祭休みなので復習したい
    -- はい，しっかりと復習をして下さい．
  • お疲れ様でした。　昼飯を買いに出かけていたら前半少し聞きそびれてしまったのでもう一度見直します
    -- はい，動画がありますので，それで復習して下さい．
  • レポート頑張ります
    -- 提出をお待ちしております．
  • 研究室配属ドキドキです
    -- ドキドキさせるよドキンちゃん，でしょうか．
  • 理論がなかなか理解できなったので、しっかり見直して理解します
    -- はい，よろしくお願いします．
  • わかりやすかったです
    -- 復習をしてわからないところがでてきたら，質問して下さい．
  • わかりやすかったです．ありがとうございました．
    -- こちらこそありがとうございます．
  • 理解に時間がかかるようになってきた
    -- 難しいことをやっているので，時間がかかるのはしかたないと思います．時間をかけて理解にいそしんで下さい．
  • コード化の辺りから復習しようと思います
    -- だいぶ前ですね．しっかりと復習をして下さい．
  • クワインについて面白そうだなと思いました。
    -- そうですね．趣味のプログラミングとしては時間をつぶせると思うので，いろいろと考えてみて下さい．
  • 証明で少しばかりこんがらがっており、理解までには時間がかかりそうです。
    -- 確かに難しいと思うので，1つ1つのステップを順に追っていって下さい．
  • 証明は追っていけば分かるのですが、どうしたらこういうものを思いつけるのかが不思議です。
    -- そうですよね．私もそう思います．だからこそ，定理と呼ばれているのだと思います．
• 11/12 (6) 停止性問題
  • コメントをありがとうございました．
  • 授業開始前にコメントが投稿され，その内容が「特になし」だったものがあります．コメントは授業終了時に投稿するべきものであり，開始前に投稿することは意味がありません．仮に，授業開始前に予習を行ない，それを受けた質問やコメントであるならば意味があるかもしれません．しかし，授業開始前に投稿されたコメントが「特になし」であっては，それによって何を伝えようとしているのか理解できません．そんな無駄なことに時間を使わないで下さい．
    
  • 特にありません。
    -- ありがとうございます．特になくてもよいので，このコメントは出し続けて下さい．
  • ありがとうございました
    -- こちらこそありがとうございます．
  • ありがとうございました。
    -- こちらこそありがとうございます．
  • ありがとうございました
    -- こちらこそありがとうございます．
  • わかりやすかったです
    -- わからないことがでてきたら，ぜひ質問をして下さい．
  • 復習します
    -- 私自身も混乱した部分があったので，スライドも修正して，動画にもコメントを付けました．復習に活かして下さい．
  • ちょっと難しかったです。
    -- そうですね．しっかりと復習して下さい．
  • 今回の内容は複雑に感じたので、よくよく復習しておきます。
    -- ぜひ演習問題にも取り組んで下さい．
  • 計算不可能な問題がたくさんあるのが興味深いと思った。
    -- そうですね．その事実はこの講義を通して学んでもらいたいことの1つです．
  • 簡単そうに見えて計算不可能なものがたくさんあるとわかって面白かったです．
    -- こういう事実はとても重要で，そもそもプログラムが作れない問題に自分が取り組んでいる可能性を常に考える必要があることに気を留めて下さい．
  • コードの正しさを検証するのは難しいことなのかなと思った。
    -- はい，そういうことになります．それが次のコメントの回答につながります．
  • isHaltingを近似的に計算する試みはなされているのか
    -- はい，なされています．私の知る限り，大きく分けて3つの流れがあると思います． 1つ目は，いわゆる「ソフトウェアの検査」とか「ソフトウェアのテスト」と呼ばれる技法につながります．これについては『ソフトウェア工学』の講義で学ぶべきことだと思うので，ここでは省略します．(シラバスによると，岩崎先生のソフトウェア工学ではテストについてやらないようですが，西先生のソフトウェア工学ではテストについてやるようです．) 2つ目は，考えるプログラムの種類を限定することです．そうすれば，停止性問題を解くことができる可能性がでてきます． 3つ目は，万能ではない計算モデルしか扱わないようにすることです．例えば，LOOPプログラムしか扱わない，とすることにします．そうすれば，必ずプログラムは停止するので，停止性問題を考える必要がなくなります．
  • isDoubleの証明でuniv(x1,x2)を行う理由がよく分からないです
    -- univ(x1, x2)を使うことで，isHaltingが計算できることを導いています．univ(x1, x2)が停止するとき，プログラムはdoubleを計算し，停止しないときdoubleを計算しない，ということになるのがポイントです．
  • isDoubleの例が分かりやすくて良かったです。
    -- 演習問題に似たものがあるので，ぜひやってみて下さい．
  • 情報領域演習のチェッカーの謎が解けました。
    -- いろいろなものの設計には，深い理由が隠れていたりするものなのです．
  • s-m-n定理便利ですね
    -- そうですね．次回も使うので，お楽しみに．
  • 前半が終わってしまうことに驚いています
    -- 前半はあと2回になりますね．後半も含めて『計算理論』の授業なので，ぜひ後半も楽しんで下さい．
• 11/5 (5) 計算可能性
  • コメントをありがとうございました．今回の内容はハイライトなので，ぜひ身につけて下さい．
  • 特になし
    -- ありがとうございます．特になくてもよいので，このコメントは出し続けて下さい．
  • 特にありません
    -- ありがとうございます．特になくてもよいので，このコメントは出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．特になくてもよいので，このコメントは出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．特になくてもよいので，このコメントは出し続けて下さい．
  • 今回はコメント忘れずに済みました
    -- それはよかったです ;-)
  • ありがとうございました
    -- こちらこそありがとうございました．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • 非常にわかりやすいです
    -- すぐに難しくなるので，わからなくなったら質問して下さい．
  • わからなくなってきた
    -- それは困りましたね．まず，何がわからないのか，ということをはっきりとさせましょう．そうすれば，質問しやすくなると思います．
  • だんだんと難しくなっていると感じているが、その都度理解度を聞いてくださるのでとてもありがたいです。
    -- はい，わからないところはぜひ質問して下さい．
  • 今回はなかなか理解が難しかったので復習をしっかりします
    -- 復習は大切ですので，励行して下さい．
  • 定義する,しないと停止する,しないが日本語的に似ていて戸惑ったが理解できた
    -- たしかにそうですね．私の発音が悪いのも問題の一端を担っているかもしれないので，気楽に質問して下さい．
  • 計算不可能な部分関数の証明がややこしかった。
    -- そうですね．大事な考え方なのでしっかりと復習をしてください．
  • 対角線論法は狐につままれたようで、ちゃんと理解できているかまだ少し不安です。
    -- ある本にも「狐につままれたよう」だと書いてあります．多くの人がそう感じるものなのだと思います．
  • 今回は質問も多く、説明自体のスピードが速くでついていくのに大変だった
    -- 質問がわからないときは，質問の内容に質問をしてもらっても全然問題ありません．
  • 今まで手書きでレポートを書いていたのですが、PCで書いたほうが楽だと気付いてPCで書くことにしました。
    -- そうなんですね．私はどちらでも大丈夫なので，お好きな方法でお試しください．
  • 寒くなってきました。体調管理にお気を付けください。
    -- ご自愛ください．
  • 今日から健康診断がありますが体重が増えてそうです><
    -- 世の中には体重を増やそうと思っても増えないという人もいるようなので，ぜいたくな悩みなのかもしれません．
  • 今年も、もうあと少しで終わりですね...
    -- まだ2ヶ月ぐらいありますよ．:-)
• 10/29 (4) コード化
  • 明日鬼滅の刃見に行きます！
    -- いいですね！ 私も見に行こうと思ってますが，いまは混んでいそうなので，もう少し日が経ってからにしようと思います．
  • 全域関数ってなんでしたっけ？
    -- 部分関数で，関数となっているもの (つまり，$f \colon A\nrightarrow B$ で，$\mathrm{dom} f = A$ であるもの) のことです．言い換えると，$f(x)\uparrow$ であるような $x$ が存在しない部分関数です．第1回講義スライドの40ページで紹介しています．
  • WHILEプログラムからGOTOプログラムへの書き換えは、簡単に感じた。
    -- 実際にやってみて下さい．そうするともっと理解できると思います．
  • カントールの対関数は頭いいと思った。
    -- そうですね．これは標準的なものなので，いろいろなところで使います．単射の構成はこれ以外にも知られていて，有名なものには，例えば「ゲーデル数化 (Gödel numbering)」というものもあります．ぜひ調べてみて下さい．
  • 少しずつ難しくなってきましたが、プログラムを考えるのに使える構文が少ないのでパズルを解いてる気分になります
    -- いっそのこと，プログラミング自体をパズルだと思ってしまえばいいと思います ;-)
  • プログラムのコード化が面白いと思った。
    -- そうですね，次回はこの考え方を使っていきます．
  • プログラムをリスト表現するという方法があるというのは面白いと思った。
    -- プログラムをコード化する方法は他にもありえると思います．ぜひ考えてみて下さい．
  • プログラムをコード化したり判定したりする方法に感動した
    -- 実際，私たちが普段書いているプログラムも，コンピュータの中では「0」と「1」だけで表されているわけで，それもコード化の1つだと見なせます．ただし，その方法は授業で紹介した方法とは違うので，注意して下さい．
  • 最後の方は理解しきれなかったところがあるので復習します。
    -- 最後の方はかけあしになってしまい，すみません．(-_-;
  • 情報量が多かったですが、なんとなくは理解できました。あとは演習問題をやって理解しようと思います。
    -- ぜひ演習問題をやってみて下さい．
  • 復習が必要だと感じた。
    -- はい，復習は大事なので，お願いします．
  • 特になし
    -- ありがとうございます．特になくてもよいので，このコメントは出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．特になくてもよいので，このコメントは出し続けて下さい．
  • 特にありません．
    -- ありがとうございます．特になくてもよいので，このコメントは出し続けて下さい．
  • ありがとうございました
    -- こちらこそありがとうございます．
  • ありがとうございます
    -- こちらこそありがとうございます．
  • わかりやすかったです
    -- わからなくなったら質問をお願いします．
  • わかりやすかったです。
    -- わからなくなったら質問をお願いします．
  • 次回が楽しみです
    -- 次回がハイライトになります．お楽しみに．
  • 証明楽しみにしています.
    -- はい，ちょっと難しいかもしれませんが，楽しみにしていて下さい．:-)
• 10/15 (3) チャーチ・チューリングの定立
  • 再レポートの提出はどこにすれば良いでしょうか
    -- 提出を行うときに開いていて，締切が一番早い「任意レポート提出」のフォームから提出して下さい．
  • しばらく引きこもっていたせいか，後期になっていろいろな気力がなくなってきて辛いです
    -- それは困りましたね．普段の生活を取り戻せるように，生活のリズムを見直して下さい．まず，朝きちんと起きることからはじめられるとよいと思います．
  • GOTOプログラム、名前は英語なのに終了はドイツ語なんですね…
    -- 「Halt」は英語にもあります．対応するドイツ語 (の原形) は「Halten」で，それが「Halt」と活用すると，命令形になります．
  • WhileとGotoの違いがよく分からなかった
    -- GOTOプログラム風のプログラムはC言語を使えば書けるので，実際に書いてみるとよいと思います．
  • goto文とif文でwhile文が表現できるのが興味深かった
    -- そうですね．こういう考え方をすることで，プログラミング言語の本質部分が見えてくる気がします．
  • GOTOプログラムのWHILEプログラムでの表し方が面白いと思いました。
    -- その逆までやりたかったのですが，時間が足りなかったので，来週やります．お楽しみに．
  • 特にありません
    -- はい，「特になし」でも，このコメントは出し続けて下さい．よろしくお願いします．:-)
  • かなり話が抽象的になってきた気がします　復習してしっかりと今後の講義について行けるようがんばります
    -- そうですね．どんどん抽象的な話になっていきます．今回，LOOP計算可能ではない話をしましたが，「可能ではない」という話をするときは，抽象的な考え方が必要になりますね．
  • 糖衣構文がたくさん出てくると理解するのに時間がかかって大変でした。
    -- そうですね．書いてあるものを理解しようとするよりも，自分で考えて作ってしまう方が分かりやすいかもしれないです．講義で紹介したものが糖衣構文を実現するただ1つの方法である，というわけではないので，他の方法を自分で考えてみることをお薦めします．
  • 計算可能性を理解することができました。
    -- それはよかったです．ぜひ演習問題にも取り組んで下さい．
  • 知っていた計算方法も勿論、知らない計算方法も学べてよかった
    -- 新しいことを学んだら，ぜひ使ってみて下さい．それができると，より深く理解できると思います．
  • とても分かりやすかったです。
    -- ありがとうございます．分かった気になるのは簡単なので，本当に分かったかどうか確認するためにも，演習問題をやってみて下さい．
  • いろいろな計算が出てきたので復習を頑張りたい。
    -- WHILEプログラムとLOOPプログラムとGOTOプログラムと混乱しそうなので，しっかりと区別して下さい．
  • whileプログラミングで考えるのがだんだん楽しくなってきた
    -- いままで勉強してきたことを組み合わせれば，WHILEプログラムのインタプリタを作ったり，WHILEプログラムをC言語のプログラムに変換するコンパイラを作ったりすることもできると思うので，ぜひ挑戦してみて下さい．
  • 計算可能性の比較が分かりやすかった。
    -- 計算可能性を比較する手法を使えるようになるのが今日の目的だったので，それが達成できたとすれば，素晴らしいです．
  • WHILEプログラム、LOOPプログラム、GOTOプログラムの関係が分かった。
    -- 今後，WHILEプログラムとGOTOプログラムの関係を使っていくことになりますので，その点はしっかりと抑えておいて下さい．
  • これほど単純な言語だと、プログラムが何を計算しているのか理解するのが難しいです。
    -- 共感します．それだからこそ，糖衣構文を導入して，わかりやすくしているつもりです．ただ，糖衣構文を導入しすぎると，それを紹介するだけで講義時間が終わってしまうので，バランスをとるのが難しいところですね．
  • プログラムが停止するということは必ずしも答えがでるということではないですよね
    -- WHILEプログラムでもLOOPプログラムでもGOTOプログラムでも，停止したときの変数 $x_0$ の値が「答え」，つまり出力であると考えています．その意味で，停止したときには必ず答えがでています．
  • LOOP x DO P ENDがLOOPプログラムである条件としてPの中にxは現れないとありますが、これはP内にxが現れるようなLOOPプログラムでないプログラムに対しては前提としてLOOP表記を使用してはならないという解釈でよろしいでしょうか？
    -- LOOPプログラムにおいて，「LOOP x DO P END」と書くとき，PはLOOPプログラムでなければなりません．つまり，P内にxが現れようが現れまいが，LOOPプログラムでないPに対して「LOOP x DO P END」と書くことはLOOPプログラムでは許されません．
  • 模倣が計算であれば、チューリング完全な計算機が自身の内部モデルを持つことはできるのか
    -- これは次回以降のテーマになります．論点は2つあります．(1) 自分自身を内部に持つ，ということは，再帰を行うことに対応します．再帰を実現するにはどうしたらよいのか，ということを後の講義の方で考えます．(2) プログラムが入力として自分自身を受け付けることを考えることができます．このときに何が起こるのか，ということが計算不可能な部分関数の存在を証明するときのカギになります．
• 10/8 (2) 計算モデル
  • コメントをありがとうございました．
  • すみません、第1回のコメントを提出するのを忘れていました。
    これこら約半年間よろしくお願いします。
    -- はい，よろしくお願いします．
  • 再来週はたしか体育祭で休講ですよね？
    -- 再来週はお休みです．
  • わかりやすかったです．
    -- ありがとうございます．
  • わかりやすかったです。
    -- すぐに難しくなるのでご注意ください．;-)
  • 説明が分かりやすかったです。
    -- 分からなくなったら質問をお願いします．
  • ありがとうございました
    -- こちらこそありがとうございました．
  • 用があって大学校舎内で受けさせてもらったのですが，ちゃんんと対策されていますね
    -- 教室では他の学生と間をあけて着席するようにご注意ください．
  • 資料が分かりやすい
    -- プログラムを2列に分けて書くか，次のページに分けて1列に書くか，かなり迷いました．1列のほうが見やすかったかもしれません．
  • よくよく復習しておきます。
    -- はい，復習は大切なので励行して下さい．
  • 一週間で課題がたまり気味になりました
    -- 演習は「課題」ではないので，やる必要はないです．でも，ぜひやってください ;-)
  • whileプログラムについてよくわかりました
    -- それはよかったです．分からないところがでてきたら，質問をお願いします．
  • 例題が多かったので理解できた。
    -- 具体例は重視しています．それが理解を助けていることが分かって，よかったです．
  • WHILEプログラム風のRubyプログラムと丁寧な説明のおかげでわかりやすかったです
    -- WHILEプログラム風のRubyプログラムを紹介しましたが，WHILEプログラム風のCプログラムでもWHILEプログラム風のJavaプログラムでもよいので，皆さんも自分で書いて動かしてみることをお薦めします．
  • While構文のみで多くの計算が可能であることがわかりました。
    -- そうですね．これで何ができて，何ができないのか，ということを探究するのがこの授業の目標です．
  • 機能を制限すると簡単なプログラムも複雑に感じられました。
    -- その気持ちはよくわかります．実際，授業の例題で扱った isEven を全部WHILEプログラムに書き換えてスライドに載せようと思ったのですが，それをやりだしたら，プログラムの行数が膨大になってしまって，結局あきらめました．(-_-;
  • whileプログラムでこう書き換えられるのかと発見でき面白かったです。
    -- こういうのを面白いと思える人は，コンピュータ・サイエンスに向いているかもしれないです ;-) (面白いと思えない人がコンピュータ・サイエンスに向いていないとは言ってないのでご注意を．)
  • あらゆる処理をwhileに落とし込むのは自分の中にない発想だと思った。
    -- 今までに自分になかった発想を知ると，勉強した気持ちになれますよね :-)
  • 簡単な計算でもすべてWHILE計算で表現するのは難しいと思いました。
    -- そうですね．ただし，ここでは「難しくても表現できる」ということが重要です．後の方では「どんなに頑張っても表現できない」ものがでてきます．
  • 今回の例は全てwhile計算可能だったができない例を具体的に知りたいです
    -- これは後の方の話題 (第5回と第6回の講義辺り) になります．お楽しみに．
  • while構文の利点、欠点を含めて説明していただけたので どうしてwhile構文を習っているのかも納得できてよかったです。
    -- 「どうして習っているのか」ということが納得できるのは大事ですね．その点が伝わってよかったです．
  • 変数の代入の実現方法が複雑に感じた。
    -- 授業中のコメントで簡単な方法を教えてもらったので，スライドを修正しました．
  • addの中にaddを埋め込む場合は変数を書いた本人の方で管理する必要があるのでしょうか？
    -- はい，その通りです．例えば「$x_4$ := add(add($x_3$, $x_5$), add($x_3$, $x_6$))」をWHILEプログラムに書き換えるときには，新しい変数$y,y'$を使って，「$y$ := add($x_3$, $x_5$); $y'$ := add($x_3$, $x_5$); $x_4$ := add($y$, $y'$)」と書くことになり (これではまだWHILEプログラムになっていませんが，addは授業で説明したように書き換えます)，$y$と$y'$を何にするのか，ということはプログラム全体を見て自分で考える必要があります．
  • isEvenでx2を加算しているのはなぜですか
    -- 説明不足でした．「IF ○○ THEN □□ ELSE △△ END」と書くとき，「□□」がWHILEプログラムでないといけないので，そこに何か書かなくてはなりません．本来はご指摘の部分では何もしなくてよいのですが，何かしないとWHILEプログラムにならないので，無駄な操作としてx2に1を足しています．
  • 休憩中に糖衣構文を使わない愚直な文を使って階乗を考えようとしたが、可読性が悪すぎてあきらめてしまった。
    -- WHILEプログラムでは，あんまり可読性を考えていないと思って下さい．別の言い方をすると，シンプルさを利点として備えるために，可読性を捨てていると思って下さい．そうであっても，WHILEプログラムで階乗を実装する，というのはよい練習になると思うので，ぜひ挑戦してみて下さい．(^^)
  • 糖衣構文でかなりの文量を省略して記述できるので、便利さを実感した
    -- そうですね．皆さんがふだん使っているプログラミング言語でも糖衣構文が多く使われています．調べてみて下さい．
  • 糖衣構文を調べると構文塩なるものがあるとわかったのですがどんなものが具体例として挙げられるのでしょうか？
    -- このサイトでは，syntactic saltの具体例として，end if，end while，end do といちいち書かないといけない (無駄な) 文法が挙げられていますね．
  • シンタックスシュガーの響きって良くないですか？
    -- わかります :-) そして，それを「糖衣構文」と訳すのも好きです．「糖衣」というのは薬にしか使わないことばだと思っていました．
  • WHILEプログラムを見て、brainfuckというプログラミング言語を連想しました。
    -- いわゆるesoteric programming languageですね．この手の言語のインタプリタを書く，という演習問題はよくあります．『Rubyで作る奇妙なプログラミング言語』という本があり，これはとてもよいです (私は初版を古書として入手しました)．「プログラミング言語を設計する」ということに興味がある人はぜひ読んでみて下さい．お薦めします．
  • 構文論と意味論は初耳だった
    -- これはプログラミング言語だけではなく，自然言語や数理論理学でも重要な概念なので，身につけて下さい．
  • 関数の未定義値を無限ループで表現することは、停止性問題と絡んでいると想像できるが、天下り的な定義に思えてしまいます。
    -- 確かに天下り的に思えますね．本来は，計算モデルを定義してから，「それが何を計算しているのか」ということを考えると，部分関数を計算していると見なせる，と進む方がよかったかもしれません．そうすると，「プログラムが停止しない」ことを「値が定義されていない」に対応させるという考え方もスッキリするかもしれません．
  • 様々な機能がWHILEプログラムの糖衣構文で表せることを聞いて、論理回路においてもNAND回路を組み合わせるだけで他の全ての論理回路を表せることを思い出しました。
    -- そうですね．いろいろな事項との類似性を見出せると理解が深まりますね．
  • ラムダ計算をハードウェア実装することは不可能なのですか?
    -- 「ハードウェア実装」ということばで何を正確に意味するのかということに依存すると思いますが，普通の計算理論における回答は「可能」になります．これは次回の内容に関わってくるかもしれませんが，「いろいろな計算モデルでできることは変わらない」ということが知られています．論理回路に基づく計算モデルはこの「いろいろな計算モデル」に含まれるので，論理回路で実装することで「ハードウェア実装」と呼ぶならば，回答は「可能」になります．
• 10/1 (1) 計算とは何か？
  • コメントありがとうございます．いただいたコメントとその回答は以下のように掲載されます．
  • よろしくお願いいたします。
    -- こちらこそよろしくお願いします．
  • 1学期の前半の間ですがよろしくおねがいします．
    -- こちらこそよろしくお願いします．
  • よろしくお願いします。
    -- こちらこそよろしくお願いします．
  • シラバスが木4になってました
    -- すみません，確認不足でした．あとで教務課の方に直してもらいます．
  • 講義の時間が学内シラバスと時間割で違っていた。
    -- すみません，確認不足でした．あとで教務課の方に直してもらいます．
  • おもしろかったので履修しようと思います。
    -- おもしろく感じていただけてよかったです．よろしくお願いします．
  • 面白い授業だと思いました
    -- 面白くなくなったら，そのときは教えて下さい．;-)
  • 今後の講義が楽しみです
    -- 私も楽しみです．(^^)
  • わかりやすかったです．
    -- 分からなくなったら，ぜひ質問して下さい．
  • 面白かったです
    -- それはよかったです．今後も面白いと思ってもらえるようにしていきます．
  • 成績評価に関わるレポートの難易度が少し気になるところですが、履修しようと思います。
    -- はい，よろしくお願いします．
  • 初めての授業でもスムーズに進めてくださってありがとうございます
    -- 最後の方で時間がなくなってしまったので，計画がよくなかったですね．すみません．
  • 後半のペースは少し大変でした
    -- 早くなってるようでしたら，授業中にぜひ指摘して下さい．よろしくお願いします．
  • 喋る内容が途切れないことに驚いた。授業の合間合間の休憩に人間味を感じた。
    -- 人間ですから．(^^;
  • 休憩をいれてくれるのはありがたいです。
    -- 休憩が不要な人は，休憩の時間に復習をして下さい．
  • 適度に休憩があるのはこちら側からしても助かります。
    -- 90分ずっと集中するというのは大変だと思います．適度に休憩しましょう．
  • この授業を受ける前からネットに落ちてる先生の資料で色々勉強させていただいたことが有るのを思い出しました...
    -- 何かしらのお役に立てているのでしたら，私もうれしいです (^^)
  • コメント機能などのサポートがあり、とても授業を受けやすいと感じました。
    -- リアルタイムの形式をとるならば，リアルタイムである意義が深くなければならないと思って，このようにしています．ぜひ活用して下さい．
  • ニ○動みたいでどこか懐かしさを感じた
    -- CommentScreenは日本の企業が開発しています．日本人にはなじみにある見栄えなのかもしれませんね．
  • コメントが流れるのが面白いと思いました。
    -- みなさん，もっとコメントをお願いします．(^-^)
  • コメントがニコニコ動画のように流れるのは楽しいけれどコメントログが残らないのは不便ですね
    -- コメントを投稿するウェブページではコメントが残り，そこで見ることができます．ただ，昔のものにさかのぼることはできません．
  • ニコニコ動画みたいにリアルタイム授業にコメントが流れる形式でとても新鮮でした。また、休憩がある分、集中して授業に参加できました。
    -- すぐ慣れるので，新鮮さは薄れると思います．;-)
  • コメントが流れてくる遠隔授業というのは初めてだったので、面白く感じました。個人的には（あまり褒められたことではないですが）声を出す必要性のなさや、カメラ非表示かつ名前も出ないため周りからの注目を浴びることがないので、対面での授業よりもリアルタイムで質問することに壁を感じそうになく、嬉しく思いました。
    -- 対面での授業でもうまく質問ができるよう，学生側も教員側も工夫が必要なのかもしれませんね．
  • 授業に出遅れてしまいコメントの仕様やこのコメント欄が重要扱いされている理由などを聴きそびれてしまいました　動画でもう一度聴いて確認したいと思います
    -- はい，よろしくお願いします．
  • 様々な媒体で再現した参考動画のおかげで抽象的な理論をより理解することが出来たと思われる
    -- 使えるものは何でも使おうと思います (^^;
  • 電子的な方法以外にも様々な方法でAND素子が実現できるということを初めて知り、驚いた。
    -- そうですね．授業で紹介したものはごく一部であって，他にもいろいろなもので論理回路を実現できます．
  • 他の講義とは違う切り口で計算機を見ることができそうで面白そうだと思いました！
    -- その側面がお届けできるように，こころがけます．
  • 今回はほとんどがガイダンスのようなものだったので、まだこの講義の内容がよく分からない点もありました。次回からの授業もまた楽しみにしています。
    -- 今日は「動機付け」の部分が多かったと思います．本格的な内容は次回から始まります．ご期待ください．
  • 演習問題の解答は後日公開されますか？
    -- 公開されません (解答を準備していません)．あしからずご了承ください．
  • 演習レポートの内容はどのような問題でもよいのですか
    -- レポートの問題は演習問題のファイルに書かれているものです．レポートには学籍番号と氏名を記載して下さい．決まった形式はありません．
  • 今までにならった関連する分野の質問をオフィスアワー等で質問することは可能でしょうか。（例えば形式言語理論や離散数学について）
    -- 可能ですが，満足にお答えできる保証はないことをご了承ください．
  • 計算を現象としてみる考えは頭になかったので、面白いと思った。
    -- そうですね．その点を今日の授業では強調できればいいな，と思いました．
  • 計算モデルについて理解できました。
    -- それはよかったです．計算モデルの例については次回以降に説明しますので，お楽しみに．
  • 計算についてまだ理解が足りてはいないのですが...「計算」という現象を構成する最小単位若しくは規定は何なのでしょうか？
    -- 計算モデルによって異なる，という回答になります．入力をとり，処理をして，出力をする，という一連の過程と見なせるものを (ここでは) 計算だと思っているのですが，種々の計算において何を最小単位とするのか，という統一見解は (今のところ) ないと思います．
    以下，私見ですが，計算理論というのは非常に未発達であると思います．世の中にある様々な計算という現象を統一的に記述する方法論をまだ我々人類は持ち合わせていないように思うのです．例えば，世の中には様々な物質があり，わけがわからない気がするのに，それらを分子や原子という単位に分けて，周期表に並べるという分類を人類は行うことによって，その多様性を統一的に記述する方法を発明しました．また，世の中には様々な生物がいて，わけがわからない気がするのに，それらはどれもDNAやRNAという物質に支配されているということを人類は明らかにしました．一方で，計算においては周期律表やDNAのような統一的法則を人類はまだ見いだせていないのだと思います．
  • ゲーデルの不完全性定理を知って計算理論に興味を持ちました。本講義では関係してくるのでしょうか。
    -- 関係はありますが，ゲーデルの不完全性定理をこの講義で扱うわけではありません．関係するのは「自己言及」という概念です．後の方の講義で扱います．
  • minecraftを教育に用いるのは賛成ですか？反対ですか？
    -- 教育効果があるならば，使えるものは何でも使えばよいと思います．つまり，条件つき賛成です．
  • 関数について忘れていたが授業で復習できたので助かった。
    -- 忘れてしまってもよいので，その点は気にしないで下さい．忘れたときに，調べて思い出せることが重要です．
  • 部分関数という概念を初めて聞いたので面白かったです。
    -- それはよかったです．;-)
  • 関数と部分関数は、写像と部分写像に似ているなと思いました
    -- 「写像」と「関数」は同じものを指す概念だと思って下さい (区別する場合もありますが)．そのため，「部分写像」と「部分関数」も同じものを指す概念だと思って下さい．
  • 部分関数に関して任意の値に対して値が存在する,存在しないを矢印の上下で表すことを学んだ。
    -- この記法は割と一般的に使いますが，覚えるほどのものではないと思います．
  • 多価関数を関数と称するのは適切なのでしょうか?
    -- 私の立場では，多価関数を関数と称するのは適切ではない，ということになります．ただ，関数といったら多価関数のことを指す，という流儀もありうると思います．

• 前半は1回のレポートにより評価を行います．
• レポート課題
• 提出締切：12月16日 (水) 23:59 JST．

• こちらをご覧ください

• 10/1 (1) 計算とは何か？
• 10/8 (2) 計算モデル
• 10/15 (3) チャーチ・チューリングの定立
• 10/22 体育祭
• 10/29 (4) コード化
• 11/5 (5) 計算可能性
• 11/12 (6) 停止性問題
• 11/19 (7) 再帰定理
• 11/26 (8) 前半のまとめ