2026年06月23日 第3回
不可能なプログラムの証明として背理法を用いるという内容であった。
作成可能なプログラムかどうか、
数学的に示せるという点が興味深かった。
最初にyesOnStringを見たときは不可能とは感じなかったが、
weirdYesOnStringを考えることで矛盾が生じることを確認し、
その証明の流れを理解することができた。
notYesOnString.py ですかね．もう一度流れを確認しておいてください．
yesOnString.pyからself-reflectionを用いたプログラムにyesOnSelf.pyを考え、
このときの"yse","no"の条件を反転させたプログラムnotYesOnSelf.pyを考えることでyesOnString.pyが存在しないことが確認できるということがわかりました。
また、
あるゆるバグを検出するプログラムcrashOnString.pyについてもself-reflectionしてわざとクラッシュする場合を想定することで、
crashOnString.pyも存在しないことが確認できるということがわかりました。
背理法以外ではどのようにして計算不可能を示すのかが気になりました。
講義ではチューリングマシンについてもお話ししますが，そこで議論しましょう．
今回の講義では、 プログラムをテキストデータとして扱い、 プログラム自身を入力として解析する「自己参照」の仕組みを学んだ。 判定プログラムの具体的な振る舞いを追うことで、 計算の限界や計算不能性への理解が深まった。
理解できてよかったと思います．
存在しないことを証明するのに、
出力を逆転させた関数を用いるという発想が面白かった。
講義では, notYesOnSelf(P)が存在しないことを利用して、
yesOnString(P,I)が存在しないことを示していたが、
その間のyesOnSelf(P)の存在についても同じように否定できるなと思った。
また、
講義で扱ったweirdOnstring(P)も直接、
notYesOnSelf(P)を作っているだけで本質的には同じだと思った。
その通りです．本質的には同じですね．
数学や哲学の「嘘つきのパラドックス」が、
Pythonコードという具体的な形で表現されていて興味深かったです。
プログラムが自分自身を判定する流れや、
出力が反転する挙動（表1〜3）を丁寧に追うことで、
コンピューターの「理論上の限界」を論理的に実感できました。
実感できたのであればよかったと思います．
今回の講義では、 yesOnString.py、 yesOnSelf.py、 notYesOnSelf.py を通して、 プログラム自身を入力として扱う自己参照の考え方について学んだ。 特に yesOnSelf.py が自身のプログラム文字列を入力として判定を行う仕組みが興味深かった。 また、 notYesOnSelf.py では yesOnSelf.py の結果を反転させることで矛盾が生じることを理解でき、 自己参照が計算理論において重要なテーマであることが分かった。
そうですね．大切となりますね．
完璧なバグ検出プログラムは存在しないことに関して、 たしかにそのようなプログラムに出会ったことはないし、 もしそのようはプログラムが存在してしまったらエンジニアなどの仕事がなくなってしまうため、 一見便利なように思えるが実は存在しないことによって人はコンピュータに仕事を奪われずに済んでいるのかもしれないと感じた。
なるほど良いコメントですね．
今回の講義では、
Pythonプログラムを入力として扱い、
そのプログラムがある入力に対して “yes” を返すかどうかを判定する問題について学びました。
yesOnString.py や yesOnSelf.py の例を通して、
プログラムも文字列として他のプログラムに渡せるという考え方が少し理解できました。
特に印象に残ったのは、
自分自身を入力として実行する P(P) の考え方です。
最初は少し不思議に感じましたが、
notYesOnSelf.py のように結果を反対にするプログラムを考えると、
矛盾が起こることが分かりました。
そのため、
すべてのプログラムについて正しく判定できるプログラムは存在しない、
という判定不能の考え方につながるのだと理解しました。
理解できたのは少しですか．．．ちょっと気になってしまいますが， 大丈夫ですかね．
自分が一番興味を持ったのは、
プログラムも結局ただの文字列だから、
プログラムを別のプログラムの入力として渡せる点でした。
count_linesにファイル名を渡して中身の行数を数える例が出てきて、
それで腑に落ちました。
さらに自分自身を入力にすることもできる、
というのも理解できました。
そのあと、
YESかNOだけ返す判定プログラムに話を絞って、
yes_on_stringからyes_on_self、
not_yes_on_selfと少しずつ作り変えていきました。
not_yes_on_selfに自分自身を入れると、
YESならNO、
NOならYESになっておかしくなるから、
こんなプログラムは存在しない、
というところは、
前にやった背理法と同じ形だと納得しました。
バグを検出するcrash_on_selfも結局同じで、
出力を逆にして矛盾を作るのが大事だと感じました。
また、
個別にバグを見つけること自体はできる、
という区別は、
勘違いしやすいと言われていたので意識して聞きました。
よろしいと思います．理解してくれたようですね．
本日の講義で導入された yesOnString.py や yesOnSelf.py のようにプログラムのソースコードそのものを文字列として扱い、
別のプログラムの入力にするという基本的な考え方は理解できました。
また、
表1や表2にあるような containsGAGA.py や yes.py といった具体的なプログラムに対して、
通常の文字列や単純なプログラムを入力した際の出力結果については、
プログラムの動作を順を追って考えることで答えを導き出すことができました。
表1の(1)のように yesOnString の入力に「'not a programT'」というような「そもそもプログラムとして成立していない文字列」を与えた場合について疑問があります。
計算論の理論的なモデルとしては単にNoを出力するという扱いになるのかと思いますが、
これを実際にPythonプログラム上で表現・実行しようとした場合、
構文エラー等でプログラム自体が異常終了してしまうことと、
正常にNoを返すことは、
理論上どのように区別して解釈するのが正しいのでしょうか？
Noを出すように設定していてNoを出すのと， 異常終了するのとは異なるので，区別できます．
本日学んだ、
yesOnself(rf('yesOnself.py'))は興味深かった。
このプログラムは、
実際には存在していないと考えられているが、
もし実行されたとしたら'yes'も'no'も出力される可能性があるというのは、
今までのプログラミングの知識では聞いたこともなかった。
また、
完全にバグを取り除くプログラムはないという話だったが、
現在利用されている-wallなどのバグ検出の仕組みが気になった。
-Wallはバグ検出ではなくてコンパイル時の警告だと思います．
使っていない変数があるよ，などですね．