計算理論から見たゲーデルとチューリング

スポンサーリンク

概要

• 論文の詳細を見る

• 本論文は述語とその長さの関係を調べ,帰納的述語は有限長で,帰納的ではない述語は本質的に無限長であることについて述べている.ゲーデルの不完全性定理の証明に用いられた証明可能性述語とチューリング機械の停止問題を表す述語は帰納的ではないから,共に本質的に無限長論理式である.前者から不完全性定理の証明が誤っていることが分る.後者からチューリング機械の停止問題が決定不能であることが直感的に理解できる.

• 2010-09-15

著者

• 田中 榮一

  Kobe University

関連論文

• 不完全性定理再考
• 計算理論から見たゲーデルとチューリング
• ゲーデル及びチューリング再考

スポンサーリンク