→ cmlrdg:至於recursively inseparable和halting problem的關係可參 12/07 21:05
→ cmlrdg:閱同樣這本書的 Theorem 3.3和其corollary :) 12/07 21:05
推 Hseuler:噢 謝謝資工強者 我研究看看XD 12/09 20:25
推 ksmrt0123:推原Po + Papadimitriou 12/10 01:37
※ 引述《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