algorithm - 理解 CheckHalt(X,X) 在 Susanna Epp 的 Discrete Mathematics with applications 定理证明中的含义

Question

我对算法有非常基本的了解。我是数学专业的毕业生。我正在阅读苏珊娜·埃普 (Susanna Epp) 的《离散数学与应用》一书中的停止问题。它有以下定理:

Theorem : There is no computer algorithm that will accept any algorithm X and data set D as input and then will output "halts" or "loops forever" to indicate whether or not X terminates in a finite number of steps when X is run with data set D.

Proof : Suppose there is an algorithm, call it CheckHalt, such that if an algorithm X and a data set D are input, then CheckHalt prints "halts" if X terminates in a finite number of steps when run with the data set D or "loops forever" if X does notterminate in a finite number of steps when run with data set D.

Now next lines are those which I don't understand in this proof

Observe that the sequence of characters making up an algorithm X can be regarded as a data set itself. Thus it is possible to consider running a CheckHalt with input (X,X).

所以我了解到，CheckHalt 本质上是作为算法 X 和数据集 D 获取输入。它告诉我们是否使用该数据集 D 运行算法 X 作为它(X 的)输入，然后 X 将停止或永远循环.因此 CheckHalt(X,D) 看起来不错。

我的问题是算法 X 如何拥有输入 X 本身，即我们如何将算法称为数据集？

“构成算法 X 的字符序列”这句话是什么意思？

我可以理解 CheckHalt(X,D)。但是什么是 CheckHalt(X,X)？

谢谢。

Answer 1

考虑以下算法来反转字符串:

function reverse(s) {
    var ret = "";
    for (var i = s.length - 1; i >= 0; i--) {
        ret = ret + s[i];
    }
    return ret;
}

它接受一个字符串作为输入，并返回一个字符串。现在考虑以下输入数据集:

"function reverse(s) {\n"
+ "    var ret = \"\";\n"
+ "    for (var i = s.length - 1; i >= 0; i--) {\n"
+ "        ret = ret + s[i];\n"
+ "    }\n"
+ "    return ret;\n"
+ "}"

这是一个字符串。它恰好是一个编码算法源代码的字符串。因为它是一个字符串，所以它是接受字符串的算法的有效输入；就像它恰好编码的算法一样。实际上，如果将此算法(的编码)传递给自身，您将获得以下明确定义的输出:

"}"
+ ";ter nruter    "
+ "}    "
+ ";]i[s + ter = ter        "
+ "{ )--i ;0 => i ;1 - htgnel.s = i rav( rof    "
+ ";"" = ter rav    "
+ "{ )s(esrever noitcnuf"

以同样的方式，如果你有一个程序 X 带有字符串编码 enc(X) 并且 X 接受一个字符串，你可以将enc(X)传递给X。如果您有另一个采用两个字符串的算法，您可以将 enc(X) 作为两个参数传递。