0

我对算法有非常基本的了解。我是数学专业的毕业生。我正在阅读 Susanna Epp 的应用程序离散数学一书中的停止问题。它有以下定理：

定理：没有计算机算法会接受任何算法 X 和数据集 D 作为输入，然后将输出“halts”或“loops forever”来指示当 X 运行数据时 X 是否以有限步数终止设置 D。

证明：假设有一个算法，称为 CheckHalt，如果输入了算法 X 和数据集 D，则 CheckHalt 打印“halts”，如果 X 在使用数据集 D 或“永远循环”，如果 X 在使用数据集 D 运行时没有在有限的步数内终止。

现在下一行是我在这个证明中不理解的那些

观察构成算法 X 的字符序列可以看作是一个数据集本身。因此，可以考虑使用输入 (X,X) 运行 CheckHalt。

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

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

句子“组成算法X的字符序列”是什么意思？

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

谢谢。

4

2 回答 2

1

Consider the following algorithm to reverse a string:

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

It takes a string as input, and returns a string. Now consider the following input dataset:

"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"
+ "}"

This is a string. It happens to be a string encoding the source of an algorithm. Because it is a string, it is a valid input to algorithms that accept strings; like the algorithm it happens to encode does. Indeed, if pass this algorithm ('s encoding) to itself, you get the following well-defined output:

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

In the same way, if you have a program X with a string encoding enc(X) and X accepts a string, you can pass enc(X) to X. If you have another algorithm that takes two strings, you can pass enc(X) as both of the parameters.

于 2017-08-09T13:22:47.010 回答
0

数据集是一个非常开放的定义，因此绝对可以想象数据集由一串字符组成。但我认为一个例子会有所帮助。

想象一下，X是一种计算.字符串中句点 ( ) 的算法。X可以用多种方式编写，但如果您想想象这种特殊方式：

  1. 从 开始计数，在 开始0位置指针0。
  2. 读取字符串中指针位置处的字符。
  3. 如果字符是 a .，则增加我们的计数。
  4. 如果字符是字符串中的最后一个字符，则返回我们的计数。
  5. 增加位置指针
  6. 返回第 2 步。

我刚刚编写的六步列表本身就是一个字符串......因此可以作为数据应用于自身（我认为我们得到了 12 个）。在这种情况下，算法可以作为数据应用于自身。

在这种情况下，CheckHalt(X,X)将返回，halt因为算法不会永远循环。

当然，并不是每个算法都能接受自己作为数据。例如，GCD 算法需要整数输入，因此它不能应用于自身。但是，我认为正在构建的反例涉及一种可以作为字符串应用于自身的算法。

于 2017-08-03T17:37:11.633 回答