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

Question

Читая обзоры Стивена Вольфрама "Новый вид науки" на Amazon, я натолкнулся на следующее утверждение:

Каждый студент, изучающий информатику (CS), знает dovetailer, очень простую двухстрочную программу, которая систематически перечисляет и выполняет все возможные программы для универсального компьютера, такого как машина Тьюринга (TM).

Может ли кто-нибудь дать «простую двухстрочную программу», которая иллюстрирует «dovetaling»?

Answer 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. Если это решение, выведите и остановитесь. Если это не так, продолжайте.

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

Answer 2

Ну, на самом деле машинная программа Тьюринга - это таблица (состояние x символ ленты), поэтому программа просто перечислит все такие возможные таблицы. вот так:

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 перечисляет все таблицы действий такого размера (например, обрабатывает таблицу как большое число и отображает как цифры). Это длиннее, чем две строки в Си, возможно, Вольфрам использовал другой, более мощный язык.