计算机能确定一个数学语句是真是假吗？

解答动态

• 

  无论是在定理中，还是在“数学陈述”中，关键都是量词。
• 

  
  首先，定理说“没有任何算法可以接受任意的数学陈述并证明它是真的这并不意味着，对于每一个数学语句，计算机都不能判断它是真是假。这仅仅意味着没有一个计算机程序可以处理所有的数学语句。
  第二个相关的细节是，他们所谈论的数学语句包括量词，例如，形式为“是否存在一个数字，使得这个数字适用于所有数字”的问题直觉告诉我们没有办法知道你什么时候完成了搜索。如果你正在寻找一个给定属性的数字，你什么时候停下来？您可以按顺序查看每个数字，但如果没有一个数字满足该属性，您将永远检查数字。
  作为一个具体的例子，目前没有人知道Collatz猜想是否正确。或者有一些数字使Collatz序列继续而没有1，或者没有这样的数字。但是没有办法问计算机是否存在这样的数字，因为我们不知道什么时候停止寻找。所以，我们不知道。
  在没有量词的情况下，大多数关于（可计算的）数字运算的数学陈述都很简单：只计算左手边，计算右手边，看看它们是否相同。但是这是一个非常有限的数学问题子集。
  
• 

  这个陈述过于宽泛，对人也过于恭维。计算机不能解决所有的问题，但人也不能。不知道为什么要增加额外的戏剧。
  这指的基本上是停顿问题的一个方面。图灵机可以确定某些问题的答案，但不能为其他问题确定答案。他们甚至提到Turing/Church.
  
• 

  一个不可判定的数学语句的简单例子是多元整数多项式是否有自然根。
  这意味着我们用自然数常量、自然数变量$n
• 

  0、\ldots、n
• 

  k$、加法、减法和乘法构建了一个表达式$E（n
• 

  0、\ldots、n
• 

  k）$。然后我们想知道$E（n\u 0，\ldots，n\u k）=0$的解是否存在。原则上，只要穷尽地搜索所有候选者，插入候选者并计算表达式，计算机就可以找到一个解。但是，不存在排除存在解决方案的一般程序。
  进一步阅读：https://en.wikipedia.org/wiki/Diophantine\u set
  
• 

  其他人已经解释了这一段引用的理论的实际意义。相反，我将讨论引用的段落是如何解释的，以便它确实正确地描述了这个理论。
  在二十世纪上半叶，数学家如库尔特·戈德尔、艾伦·图灵和阿隆佐·丘奇发现，某些基本问题——无法用计算机解决。这种现象的一个例子是确定一个数学语句是真是假的问题。
  这一部分的关键点是，“一个数学语句”不是指任何特定的语句，甚至不是指尚未指定的语句。&“数学陈述”是描述问题的一个输入，它可以给出任何与描述相匹配的任意值，而真正解决问题需要指定一个解决方案，该解决方案将适用于该输入的每一个可能值。
  这项任务是数学家的生计。这似乎是一个自然的解决办法，由计算机，因为它是严格的范围内的数学。但是没有一种计算机算法可以完成这项任务。
  这一段令人困惑地使用短语“this task”来表示不同地方的不同事物，其中只有一个与前面描述的问题相匹配。
  确定一个特定数学陈述是真是假的任务是真的数学家的面包和黄油，以及对单个输入值的问题的应用，是“this task”的第一个用法所指的。
  “this task”的另一个用法是指我上面描述的一般情况，即为每个可能的输入值解决问题，因此，无论你用什么样的输入值，你的解都能得到正确的答案。
  一般情况下的任务对计算机是不可能的，对数学家也是不可能的。事实上，这根本不可能。这样一来，一般案件无论如何也无法完全解决，关于这一点，最值得注意的是，这一深刻成果的结果之一，是有关计算机理论模型的思想的发展，这些思想最终将有助于构建实际的计算机。本节将继续讨论另一个主题，与理解这里的问题无关。
  
• 

  基于可计算性的广义不完全性定理及其应用
• End