ゲーデル及びチューリング再考

• Item type: SIG Technical Reports(1)
• 公開日: 2010-09-15
• タイトル: ゲーデル及びチューリング再考
• タイトル / 言語: en
• タイトル: Reflections on Gödel and Turing
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Kobe University
• 著者所属(英): en
• 著者所属(英): Kobe University
• 著者名: 田中, 榮一
• 著者名(英): Eiichi, Tanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ゲーデルの第一不完全性定理は，算術の体系に証明も反証もできない有限長論理式がある，と主張している．本文ではゲーデルが定理の証明に用いた論理式は本質的に無限長であることを明らかにした．ゆえに第一不完全性定理の証明は正しくない．しかし，本質的に無限長である論理式は証明も反証もできないから，本質的に無限長である論理式を持つ体系は不完全である．算術の体系にも本質的に無限長である論理式があるから，算術の体系は不完全である．チューリング機械の計算を表す論理式も本質的に無限長であるから，停止問題が決定不能であるのは当然である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Gödel’s first incompleteness theorem on Peano arithmetic states that there exists a finite length formula that can be neither proved nor refuted. This paper clarifies that the formula that Gödel used in his proof is an essentially infinite length formula. This means that the proof of the first incompleteness theorem is incorrect. Nevertheless, the incompleteness theorem holds in any formal system with essentially infinite length formulas. Since the arithmetic includes essentially infinite length formulas, it is incomplete. The formula to express the halting problem of a Turing machine is also an essentially infinite length formula. Therefore it is natural that the halting problem is undecidable.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2010-AL-131, 号 12, p. 1-6, 発行日 2010-09-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会