是否有圖靈機停機概率和3 CNF SAT之間的關係？

圖靈機停機問題& 3 CNF SAT？我找不到算法的任何書籍它們之間的關係是什麼？是否有圖靈機停機概率和3 CNF SAT之間的關係？

他們是不同的問題。停機問題是關於「機器不可能（不存在）決定圖靈機是否停止輸入」。 3 CNF SAT是關於「一類問題的硬度（但仍然可以解決），在多項式時間內無法解決（至今）」 – justhalf

我確實這麼認爲。這是沒有道理的，但我的老師說，如果一個圖靈機等價於計算機程序，它們之間會有關係，我不知道這個問題T^T – user2830666

那麼你是否試圖找到「圖靈機和3CNF SAT「或」暫停問題和3CNF SAT「？ – justhalf

暫停問題比較困難。

3-SAT是NP-complete，而在一般情況下停止問題是不可判定的。換句話說，不可能制定算法來解決圖靈機上的一般暫停問題。

一個直覺爲什麼停止問題可以像在圖靈機上解決任何決策問題一樣困難。你可以爲一個疑難問題編寫一個求解器，如果它找到了答案就停下來，然後詢問這個求解器是否會停下來。

2013-09-30 09:41:20 Adam

「可以做任何存在的決策問題一樣困難」有點沒有幫助（如果不是不正確的話），因爲停止問題的核心結論是可以解決暫停問題的機器的**不存在**。 – justhalf

好點，我會換個話。 – Adam

「停滯的問題更難」也很模糊，因爲它實際上**不能被解決。哈哈。這就好像說「走在陽光下比在南極游泳更難」，如果人們不知道這是不可能的，它仍然會試圖從中解脫出來。 – justhalf

在圖靈機上無法解決暫停問題，而3SAT可解決。你還在尋找其他什麼樣的關係？

2013-09-30 09:44:49 xuanji

我這麼認爲。這是沒有道理的，但我的老師說，如果一個圖靈機等價於計算機程序，它們之間會有關係，但我不知道T^T – user2830666

停機問題是什麼語言可以被圖靈機識別，甚至有無限的時間。這是非常合乎邏輯的問題。

3SAT問題是需要多少操作才能解決問題，這意味着需要多少時間。這是一個關於尋找快速算法的問題，因爲已知存在慢算法。

2013-09-30 09:50:52

回答