Понимание значения CheckHalt(X,X) в доказательстве теоремы Дискретной математики Сусаны Эпп с приложениями

Question

У меня есть очень простое знакомство с алгоритмами. Я выпускник по математике. Я читал проблему остановки в книге "Дискретная математика с приложениями" Сюзанны Эпп. Имеет следующую теорему:

Теорема: не существует компьютерного алгоритма, который принимал бы любой алгоритм X и набор данных D в качестве входных данных, а затем выводил бы "остановки" или "циклы навсегда", чтобы указать, заканчивается ли X конечным числом шагов, когда X выполняется с данными набор D.

Доказательство. Предположим, что есть алгоритм, назовите его CheckHalt, так что если вводится алгоритм X и набор данных D, то CheckHalt выводит "halts", если X завершается за конечное число шагов при запуске с набором данных D или " циклы навсегда ", если X не заканчивается за конечное число шагов при запуске с набором данных D.

Теперь следующие строки - это те, которые я не понимаю в этом доказательстве.

Обратите внимание, что последовательность символов, составляющая алгоритм X, может рассматриваться как сам набор данных. Таким образом, можно рассмотреть запуск CheckHalt с вводом (X,X).

Итак, я понял, что CheckHalt, по сути, получает входные данные в виде алгоритма X и набора данных D. Он говорит, если мы запустим алгоритм X с этим набором данных D в качестве входного (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) как оба параметра.

Answer 2

Набор данных - это довольно открытое определение, поэтому должно быть вполне возможно, что набор данных будет состоять из строки символов. Но я думаю, что пример поможет.

Представьте, что X - это алгоритм подсчета периодов (.) в строке. X может быть написано любым количеством способов, но если вы хотите представить себе этот конкретный способ:

1. Начните отсчет с 0 и указатель положения на 0,
2. Прочитайте символ в позиции указателя в строке.
3. Если персонаж .Увеличьте наш счет.
4. Если символ является последним символом в строке, вернуть наш счетчик.
5. Увеличить указатель позиции
6. Вернитесь к шагу 2.

Список из шести шагов, который я только что написал, сам по себе является строкой... и, таким образом, может применяться к себе как к данным (я думаю, что мы получаем 12). В этом случае алгоритм может быть применен к самому себе как данные.

В этом случае, CheckHalt(X,X) вернется halt поскольку алгоритм не зацикливается вечно.

Конечно, не каждый алгоритм сможет принять себя в качестве данных. Например, алгоритм GCD требует целочисленного ввода, поэтому он не может быть применен к самому себе. Тем не менее, я предполагаю, что создаваемый встречный пример включает в себя алгоритм, который может быть применен к самому себе как строка символов.