バカ犬を使った停止性問題のわかりやすい例え
- チューリングマシンとかの話で出てくる停止性問題について、とてもわかりやすいたとえ話を聞いたので紹介。
停止性問題
停止性問題（ていしせいもんだい）は、（直接的には）計算可能性理論の問題で、チューリング機械（≒プログラム、アルゴリズム）Aに入力xを入れたら有限時間で停止するか、という問題。アラン・チューリングは1936年、停止性問題を解くチューリング機械が存在しない事を対角線論法で示した。すなわちそのようなチューリング機械の存在を仮定すると、自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止するような別のチューリング機械が構成できるという矛盾が導かれる。
(Wikipedia)
- 単純にいえば、「与えられたプログラムが停止する」ということを判断し停止するプログラムは書けないということ。
- なぜなら、もし、そういったプログラムが存在するようであれば、結果をひっくり返した「与えられたプログラムが停止する場合以外のみ停止するプログラム」がかけるからである。
- 何がおかしいかといえば、そのプログラム自身をそのプログラムに与え判断しようとした場合、
- そのプログラムが停止するとすると、その与えられたプログラムは停止しないはずであり矛盾が生じ、
- 逆に、そのプログラムが停止しないとすると、その与えられたプログラムは停止するはずであり矛盾が生じる
- 理論的にわかっても、ん？？ほんとに？となりやすいこの問題にいいたとえ話を聞いたので紹介
バカ犬のお話
弱い犬ほど良く吠えるというが、バカな犬はそれ以上にたちが悪い。
窓ガラスや水たまりに映った自分の姿にもワンワン吠えるからだ。
Aさんは保健所から「バカ犬」とそうでない犬とを分ける作業を頼まれていた。
そこで彼は、自分の飼っている利口な犬レオに、その仕分けをさせることを思いついた。
方法は単純。保健所の犬たちに鏡を見せ、自分の姿を見て吠える犬を「バカ犬」とし、「バカ犬」であるならばレオにワンと吠えさせて選別した。
あっという間に、たくさんいた犬は賢いレオによって選別された。
明くる日、その話を聞いたあるペットショップのオーナーが、たくさんいる犬の中から「バカ犬」じゃない犬を選び出したいという話をAさんに持ちかけた。
そこでAさんは、レオに「自分の姿を見て吠えない犬」だけにワンと吠えさせて選別した。
こうして、レオは「賢い犬を見分けて吠える犬」として話題となった。
そこに現れたのが、アラン・チューリングだった。
鼻高々にレオを自慢するAさんの前で、レオに一枚の鏡を立てこう聞いた。
「この犬は賢いかい？」
