Re: [請益] 一階邏輯的不可判定
※ 引述《cmlrdg (心之語)》之銘言：
: ※ 引述《Hseuler (藍色貍貓)》之銘言：
: : 要如何證明?
: : 和停機問題有關係嗎?
: : 謝謝
: ( 其中N為自然數系的model;
: NT為自然數系的公理集合;
: 1. "UNSATISFIABLE SENTENCES" 和 "NT |﹣φ"
: 這兩個languages是recursively inseparable.
: (意思就是不存在一個recursive language可將兩者分開;
: 如果存在如此language, 則halting problem將為decidable) ▓
: 2. 由1.我們也因此而得知下述結果:
: 給定一個first order的sentence, φ
: 以下三個problems皆為undecidable:
: a) "VALIDITY," 也就是, "φ是否為valid?";
: b) "N |﹦φ?";
: c) "{NT} |﹣φ?".▓
這裡我不是很懂, 原po問的應該是first order logic的undecidability,
這裡給的似乎是要比自然數系(Peano Arithmetics)強的系統,
所以應該是無法用來證明一階邏輯的不可判定性。
: 原po所問的, 應該就是上面的a)這個問題了.
: 詳情可參閱
: Computational Complexity, by Christos H. Papadimitriou
: 的6.3節, 上述之定理取自其 Theorem 6.3 和 Corollary 1,
: 這本書裡皆有詳細的說明和證明!
: P.S. 他下一頁的 Corollary 2
: 即為赫赫有名的Godel's Incompleteness Theorem... XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 131.111.224.87
討論串 (同標題文章)