您如何证明一个简单的无意义代码是否可计算？

Question

可计算问题的特征是：

如果我错了请纠正我，我通过研究发现除了 deterministic.

之外并不完全知道它的实际含义

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

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

是可计算的。

我知道如何证明它是确定性，因为它相当明显，但我不确定如何证明它是机械性或完成.

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

但是对于上面的代码片段，我该如何证明它是完整的呢？

至于机械“1 + 1 = 2而不是3吗？”。

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

Answer 1

你混淆了一些东西。

首先，你提供了一段代码，问如何证明它是可计算的。但这没有任何意义-一段代码无法计算或不可计算。

A（数学）集合可以是可计算的，也可以是不可计算的。基于此，其他所有内容也是一个集合：例如语言（这是一组字符串），决策问题（这是一组接受的输入）或函数（这是一组键值对）。

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

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

一个问题是可计算的当且仅当存在解决它的算法。
一个算法解决了一个问题当且仅当
- 它可以在标准计算模型（例如图灵机或标准编程语言）中表达；
- 关于问题合理：算法产生的任何答案都属于问题的答案集；
- 本题完整：本题答案集的任意元素均由算法生成；
- 算法在所有输入上停止。

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

How do you prove whether a simple unmeaningful code is computable or not?