作者MathTurtle (恩典)
看板logic
标题Re: [请益] 一阶逻辑的不可判定
时间Mon Dec 8 03:18:53 2008
※ 引述《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