計算機能確定一個數(shù)學(xué)語句是真是假嗎？

解答動態(tài)

• 

  無論是在定理中，還是在“數(shù)學(xué)陳述”中，關(guān)鍵都是量詞。
• 

  
  首先，定理說“沒有任何算法可以接受任意的數(shù)學(xué)陳述并證明它是真的這并不意味著，對于每一個數(shù)學(xué)語句，計算機都不能判斷它是真是假。這僅僅意味著沒有一個計算機程序可以處理所有的數(shù)學(xué)語句。
  第二個相關(guān)的細(xì)節(jié)是，他們所談?wù)摰臄?shù)學(xué)語句包括量詞，例如，形式為“是否存在一個數(shù)字，使得這個數(shù)字適用于所有數(shù)字”的問題直覺告訴我們沒有辦法知道你什么時候完成了搜索。如果你正在尋找一個給定屬性的數(shù)字，你什么時候停下來？您可以按順序查看每個數(shù)字，但如果沒有一個數(shù)字滿足該屬性，您將永遠(yuǎn)檢查數(shù)字。
  作為一個具體的例子，目前沒有人知道Collatz猜想是否正確。或者有一些數(shù)字使Collatz序列繼續(xù)而沒有1，或者沒有這樣的數(shù)字。但是沒有辦法問計算機是否存在這樣的數(shù)字，因為我們不知道什么時候停止尋找。所以，我們不知道。
  在沒有量詞的情況下，大多數(shù)關(guān)于（可計算的）數(shù)字運算的數(shù)學(xué)陳述都很簡單：只計算左手邊，計算右手邊，看看它們是否相同。但是這是一個非常有限的數(shù)學(xué)問題子集。
  
• 

  這個陳述過于寬泛，對人也過于恭維。計算機不能解決所有的問題，但人也不能。不知道為什么要增加額外的戲劇。
  這指的基本上是停頓問題的一個方面。圖靈機可以確定某些問題的答案，但不能為其他問題確定答案。他們甚至提到Turing/Church.
  
• 

  一個不可判定的數(shù)學(xué)語句的簡單例子是多元整數(shù)多項式是否有自然根。
  這意味著我們用自然數(shù)常量、自然數(shù)變量$n
• 

  0、\ldots、n
• 

  k$、加法、減法和乘法構(gòu)建了一個表達(dá)式$E（n
• 

  0、\ldots、n
• 

  k）$。然后我們想知道$E（n\u 0，\ldots，n\u k）=0$的解是否存在。原則上，只要窮盡地搜索所有候選者，插入候選者并計算表達(dá)式，計算機就可以找到一個解。但是，不存在排除存在解決方案的一般程序。
  進一步閱讀：https://en.wikipedia.org/wiki/Diophantine\u set
  
• 

  其他人已經(jīng)解釋了這一段引用的理論的實際意義。相反，我將討論引用的段落是如何解釋的，以便它確實正確地描述了這個理論。
  在二十世紀(jì)上半葉，數(shù)學(xué)家如庫爾特·戈德爾、艾倫·圖靈和阿隆佐·丘奇發(fā)現(xiàn)，某些基本問題——無法用計算機解決。這種現(xiàn)象的一個例子是確定一個數(shù)學(xué)語句是真是假的問題。
  這一部分的關(guān)鍵點是，“一個數(shù)學(xué)語句”不是指任何特定的語句，甚至不是指尚未指定的語句。&“數(shù)學(xué)陳述”是描述問題的一個輸入，它可以給出任何與描述相匹配的任意值，而真正解決問題需要指定一個解決方案，該解決方案將適用于該輸入的每一個可能值。
  這項任務(wù)是數(shù)學(xué)家的生計。這似乎是一個自然的解決辦法，由計算機，因為它是嚴(yán)格的范圍內(nèi)的數(shù)學(xué)。但是沒有一種計算機算法可以完成這項任務(wù)。
  這一段令人困惑地使用短語“this task”來表示不同地方的不同事物，其中只有一個與前面描述的問題相匹配。
  確定一個特定數(shù)學(xué)陳述是真是假的任務(wù)是真的數(shù)學(xué)家的面包和黃油，以及對單個輸入值的問題的應(yīng)用，是“this task”的第一個用法所指的。
  “this task”的另一個用法是指我上面描述的一般情況，即為每個可能的輸入值解決問題，因此，無論你用什么樣的輸入值，你的解都能得到正確的答案。
  一般情況下的任務(wù)對計算機是不可能的，對數(shù)學(xué)家也是不可能的。事實上，這根本不可能。這樣一來，一般案件無論如何也無法完全解決，關(guān)于這一點，最值得注意的是，這一深刻成果的結(jié)果之一，是有關(guān)計算機理論模型的思想的發(fā)展，這些思想最終將有助于構(gòu)建實際的計算機。本節(jié)將繼續(xù)討論另一個主題，與理解這里的問題無關(guān)。
  
• 

  基于可計算性的廣義不完全性定理及其應(yīng)用
• End