TOC 中可计算和不可计算的问题
可计算问题– 你熟悉许多可计算(或可判定)的问题(或函数)，这意味着存在某种算法，可以在有限数量的简单步骤中计算问题的任何实例(或函数的任何输入)的答案(或输出)。一个简单的例子是整数增量操作:
f(x) = x + 1
应该很直观，给定任意整数 x，我们可以在有限步数内计算 x + 1。因为 x 是有限的，所以它可以用有限的数字串来表示。利用我们都在学校学过的加法方法(或算法)，我们可以很清楚地计算出另一串数字，代表相当于 x + 1 的整数。
然而，也存在不可计算(或不可判定或不可计算)的问题和函数，这意味着不存在能够在有限数量的简单步骤中计算所有输入的答案或输出的算法。(不可判定只是指在决策问题的上下文中不可计算，其答案(或输出)不是“真”就是“假”)。
不可计算的问题– 不可计算的是一个没有算法可以用来解决的问题。不可计算性(或不可判定性)最著名的例子是停顿问题。给出一个图灵机及其初始输入的描述，确定程序在这个输入上执行时是否曾经停止(完成)。
另一种选择是它永远不停地运行。停机问题是看一台机器在某个输入被输入时是否会停止，或者它是否会完成运行。这个输入本身可以是一个永远不停地调用自己的东西，这意味着它将导致程序永远运行。
另一个不可理解问题的例子是:确定计算机程序是否在某个输入上永远循环。如果你了解图灵机，你可以用“图灵机或算法”来代替“计算机程序”。
证明可计算性还是不可计算性– 我们可以通过描述一个过程，证明这个过程总是终止，并且总是产生正确的答案，来说明一个问题是可计算的。这足以提供一个令人信服的论点，即这种程序的存在发现实际程序是不必要的(但往往有助于使论点更有说服力)。
为了证明一个问题是不可计算的，我们需要证明不存在解决这个问题的算法。由于可能的程序有无限多种，我们不能只列出所有可能的程序，并说明为什么每一个程序都不能解决问题。相反，我们需要构建一个论证，表明如果有这样的算法，它将导致矛盾。
我们争论的核心是基于知道停顿问题是不可争辩的。如果一个新问题的解可以用来解决暂停问题，那么我们知道 P 也是不可计算的。也就是说，不存在可以求解 P 的算法，因为如果存在这样的算法，它也可以用来求解我们已经知道不可能的停止问题。证明某个问题 P 的解可以用来解决另一个问题 Q 的证明技术被称为约简。问题 Q 是可化约的为问题 P，如果问题 P 的解可以用来解决问题 Q。这意味着问题 Q 不比问题 P 难，因为问题 Q 的解导致问题 P 的解
关于可计算问题的一些例子– 这是可计算问题的四个简单例子:
- 计算一对整数的最大公约数。
- 计算一对整数的最小公倍数。
- 求有限图中一对节点之间的最短路径。
- 确定命题公式是否是重言式。
关于可计算问题的一些例子–状态输入问题。 考虑确定一个字符串‘w’给某个图灵机‘M’是否会进入某个状态‘q’的问题(其中 q 属于图灵机 M 中所有状态的集合，字符串 w 不等于空字符串)。是可计算的还是不可计算的？
解释– 我们通过展示状态进入问题和停顿问题一样难，来展示状态进入问题是不可计算的，我们已经知道停顿问题是不可计算的。
状态输入问题是在给定的字符串上问我们，如果我们从图灵机的初始状态开始，它会达到状态 q 吗？现在这个状态输入问题可以转化为暂停问题。停止问题是我们的图灵机是否曾经停止，状态输入问题是问同样的问题，如果我们给字符串 w 作为图灵机 m 的输入，这个图灵机是否在某个状态 q 停止。所以状态输入问题是不可计算的，因为我们把它转换成停止问题，我们已经知道这是不可计算的问题。这样我们就可以证明不可计算性。
版权属于：月萌API www.moonapi.com，转载请注明出处
