Ledの日記: 停止するか判定できないような関数
日記 by
Led
このコメントの話、このコメントの口調は妙に防衛的に感じるし、親コメントACを擁護したいわけでもなく、直接かかわりたくないので「ログインユーザーのみ」の日記で。
「停止するか判定できないような関数」には「チューリング機械の空入力停止問題」とかいうのがあるらしい。要するにC言語で適当にチューリング機械の定義を与えておいて、空入力でのTMの動作を模倣する関数が該当する。ある程度ゴチャゴチャしたものを作ってやれば、人間が見て判断するのはコスト的に無理になる。機械で判定しようとしても、十分長い時間たった後で停止するTMと、永遠に停止しないTMを区別することができない。
他にもPostの対応問題とかいうのがあるらしい。
停止するか判定できないような関数 More ログイン