Что подразумевается под "ласточкин хвостом"?

Ответ 1

У студента CS обычно есть под рукой кодирование машин Тьюринга целым числам, которые им нужны, когда они пишут свое программное обеспечение эмулятора машины Тьюринга, которое принимает на входе машину Тьюринга и записывает в качестве вывода выходной сигнал указанной машины. Возможно, чтобы это кодирование обладало свойством, что каждое целое является другой, действующей программой.

Таким образом, наивный двухстрочный список для списка и выполнения всех программ будет:

for (int i = 0; ; ++i) 
    printf("%d: %d\n", i, universal_turing_machine(i));

Это игнорирование того, что в C, int является типом фиксированной ширины.

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

Я не знаю, как это "двухстрочный", учитывая контекстный переключатель, необходимый между машинами Тьюринга на каждом шаге. Но программа "ласточкин хвост" имеет теоретическое применение (и, вероятно, практически не используется). Интересно, что он обладает следующим свойством:

Если существует программа P, которая решает проблема X в полиномиальное время (и предоставляет информацию, необходимую для доказательства решения), то программа "ласточкин хвост" решает X в полиномиальное время.

Доказательство довольно просто (требуется постоянное время, эквивалентное выполнению команд P*(P-1)/2 Тьюринга, чтобы достичь начала правильной программы P [*], а затем только полиномически худшее время для ее выполнения, чем потребовалось бы выполнить эту программу самостоятельно). Повторное утверждение свойства, которое я нахожу наиболее забавным, это:

Если P = NP, то мы уже знаем полиномиальные решения для всех NP-полные проблемы.

Мы еще не доказали, что они многочлены. Доказательство P = NP завершило бы это доказательство, фактически не демонстрируя, какая из подпрограмм это решение этой проблемы. Сама программа "ласточкин хвост" может понять, как это происходит - когда каждая машина останавливается, используйте полиномиальное время "- это решение для X для исходного ввода?" алгоритм, который подразумевает, что X является NP. Если это решение, выход и остановка. Если это не так, продолжайте.

[*] Ну, может быть, линейное время, так как при создании каждой новой виртуальной машины Тьюринга вам нужно предоставить ей копию ввода для работы. Также на практике переключатели контекста, вероятно, не являются постоянным временем, поэтому назовите его квадратичным. Ручная волна-рука-это полином OK?

Ответ 2

Ну, программа машины turing - это, фактически, таблица (state x tape symbol), поэтому программа просто перечислит все такие возможные таблицы. например:

for(int symbol_count = 1; true; symbol_count++)
{
    for(int state_count = 1; state_count <= symbol_count; state_count++)
    {
        gen_table(symbol_count, state_count);
    }
}

где gen_table перечисляет все таблицы действий такого размера (например, рассматривая таблицу как большое число и указывается как цифры). Дольше, чем две строки в C, вероятно, Вольфрам использовал другой, более мощный язык.