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

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

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

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

Источник

2 ответа

Решение

Студент 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 это полиномиальный ок?

Источник

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

Источник
Другие вопросы по тегам