作者cmlrdg (心之语)
看板logic
标题Re: [请益] 一阶逻辑的不可判定
时间Sun Dec 7 21:02:23 2008
※ 引述《Hseuler (蓝色狸猫)》之铭言：
: 要如何证明?
: 和停机问题有关系吗?
: 谢谢
个人提供粗浅的所学知识:
下图中
1), 2), 3), 4), 5), 一共五条界线
皆不为recursive.
---------------------------------------
| VALID SENTENCES ( |﹦φ) |
1) ---------------------------------------
| NT |﹣φ |
2) ---------------------------------------
| N |﹦φ |
3) ---------------------------------------
| N |﹦～φ |
4) ---------------------------------------
| NT |﹣～φ |
5) ---------------------------------------
| UNSATISFIABLE SENTENCES ( |﹦～φ) |
---------------------------------------
( 其中N为自然数系的model;
NT为自然数系的公理集合;
"VALID SENTENCES" 是 "NT |﹣φ" 的subset;
"NT |﹣φ" 是 "N |﹦φ"的subset;
"UNSATISFIABLE SENTENCES" 是 "NT |﹣～φ" 的subset;
"NT |﹣～φ" 是 "N |﹦～φ"的subset. )
上述的论断来自於底下的定理:
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所问的, 应该就是上面的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: 140.112.5.39
1F：→ cmlrdg:至於recursively inseparable和halting problem的关系可参 12/07 21:05
2F：→ cmlrdg:阅同样这本书的 Theorem 3.3和其corollary :) 12/07 21:05
3F：推 Hseuler:噢 谢谢资工强者 我研究看看XD 12/09 20:25
4F：推 ksmrt0123:推原Po + Papadimitriou 12/10 01:37