0

可计算问题的特征是：

  • 完整意味着它涵盖了所有情况；
  • 机械意味着它是精确的；
  • 确定性意味着如果输入相同的输入，将提供相同的输出。

如果我错了，请纠正我，我通过研究发现除了确定性之外并不完全知道它的实际含义。

所以，我试图证明一个简单的代码，例如：

int i = 0;
do{
    int j = 0;
    do{
        printf("Hello\n");
        j++;
    }while (j < n);
    printf("Hello\n");
    i++;
}while (i < n);

是可计算的。

我知道如何表明它是确定性的，因为它相当明显，但我不确定如何表明它是mechanistic或complete。

Complete特性，据我了解，它更像是“代码是否有任何方式无法执行或作为错误返回？” 例如打开一个文本文件有可能文件不存在，因为输入了错误的文件名或输入了错误的位置等。

但是在上面的代码片段的情况下，我应该如何证明它是完整的？

至于机制“是否 1 + 1 = 2 而不是 3？”。

同样的事情，对于上面的代码片段，我如何证明它是精确的，因为代码本身并没有解决任何问题，它只是根据 n 值打印“hello”？在这种情况下，n^2 + n 个“你好”。

4

1 回答 1

2

你混淆了一些东西。

首先，您提供了一段代码并询问如何证明它是可计算的。但这没有任何意义——一段代码不能计算或不可计算。

（数学）集合可以是可计算的或不可计算的。在此基础上，其他一切也是一个集合：例如一种语言（它是一组字符串）、一个决策问题（它是一组接受的输入）或一个函数（它是一组键值对）。

其次，您提到的“特征”并未定义可计算的问题。我不知道你从哪里得到它们，但它们充其量只是对用于解决可计算问题的算法的某些方面的非常非正式的描述。所以我认为你不是在谈论可计算的问题，而是在谈论算法。但是鉴于您的特征是非正式的，您无法证明它们。

所以这里有一些稍微更精确（但仍然不是正式）的陈述可能会有所帮助：

  • 如果存在解决该问题的算法，则该问题是可计算的。
  • 算法解决问题当且仅当
    • 它可以在标准计算模型（例如图灵机或标准编程语言）中表达；
    • 就问题而言是合理的：算法产生的任何答案都属于问题的答案集；
    • 就问题而言是完备的：问题答案集中的任何元素都是由算法产生的；
    • 算法在所有输入上停止。

现在，这些特征足够精确，您可以实际使用它们来证明问题是可计算的，或者算法可以解决特定问题。

于 2020-11-18T20:25:09.567 回答