パスワードを忘れた? アカウント作成
13456909 journal
数学

Ledの日記: 停止するか判定できないような関数

日記 by Led

このコメントの話、このコメントの口調は妙に防衛的に感じるし、親コメントACを擁護したいわけでもなく、直接かかわりたくないので「ログインユーザーのみ」の日記で。

「停止するか判定できないような関数」には「チューリング機械の空入力停止問題」とかいうのがあるらしい。要するにC言語で適当にチューリング機械の定義を与えておいて、空入力でのTMの動作を模倣する関数が該当する。ある程度ゴチャゴチャしたものを作ってやれば、人間が見て判断するのはコスト的に無理になる。機械で判定しようとしても、十分長い時間たった後で停止するTMと、永遠に停止しないTMを区別することができない。

他にもPostの対応問題とかいうのがあるらしい。

この議論は、Led (7726)によって ログインユーザだけとして作成されたが、今となっては 新たにコメントを付けることはできません。
typodupeerror

日本発のオープンソースソフトウェアは42件 -- ある官僚

読み込み中...