運営元のロゴ Copyright © 2007-2024 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
論理と計算のしくみを読んでいてチューリングマシンの停止性問題(Halting problem)の証明がしっくり来なかったので、Rubyで書いてみました。こうして書いてみると、証明のアイデアとしては単純明快です。 ちなみに、Lisper のためのチューリングマシンの停止性問題にて書かれている話とほぼ同じ内容です。 証明 停止性問題ってのはものすごく簡単に言えば『「プログラム"machine"に引数"input"を渡した時、無限ループせずに停止するか」を判定するプログラムは書けない』ってことです。このプログラム"halts?"が書けた物として、矛盾を導きます。 halts?が書けたと仮定すると、これを元にして以下のようなプログラムを書くことができます*1。 def my_machine(input) if halts?(input, input) then while true # runs
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く