Нижняя граница числа оракулов, требующих решения

Я столкнулся со следующим вопросом, который является легким упражнением (спойлер ниже).

Нам дают $n$экземпляры проблемы остановки (т. е. ТМ ), и нам нужно решить, какие именно из них останавливаются на . То есть нам нужно вывести . Нам дан оракул для решения проблемы остановки, но мы должны использовать его минимальное количество раз.$M_1,...,M_n$$\epsilon$$\{i: M_i\text{ halts on }\epsilon\}$

Нетрудно показать, что это можно сделать с помощью вызовов .$\log (n+1)$

Мой вопрос: можем ли мы доказать нижнюю границу? Есть ли основания подозревать, что такую ​​границу будет очень трудно найти?

Ответ на сам вопрос (спойлер, наведите мышь):

Рассмотрим случай $3$TMs. Мы можем построить ТМ$H_2$ это работает $M_1,M_2,M_3$параллельно, и останавливается, если по крайней мере два из них останавливаются (в противном случае он застревает). Точно так же мы можем построить ТМ$H_1$это останавливает, если хотя бы один из них останавливается. Затем мы можем назвать оракула на$H_2$, Если он останавливается, мы можем запустить машины параллельно и подождать, пока один из них остановится. Затем мы можем назвать оракула последним. Если оракул говорит «нет», то мы запускаем оракула на$H_1$, Если он останавливается, мы запускаем машины до тех пор, пока он не остановится, а остановится только один. Если$H_1$не останавливается, то никто из них не останавливается. Расширяя это до$n$ машины это просто.

Первое замечание по этому вопросу состоит в том, что, кажется, невозможно решить с помощью теоретико-информационных инструментов, поскольку мы в значительной степени полагаемся на нашу способность получать информацию, запустив машины без оракула.

Результат можно найти в

• Beigel, R., Gasarch, WI, Gill, J., и Owings, J. Terse, superterse и подробные множества . Сообщить. и компьютер. 103 (1993), нет. 1, 68–85.

Их доказательство фактически показывает, что ваша проблема не может быть решена с помощью менее $\log_2 n$запросы к любому набору$X$не говоря уже о самой проблеме остановки. Для некоторых обозначений ваша проблема иногда обозначается$C_n^K$ или $C_n^{HALT}$ (в зависимости от вашего любимого обозначения для проблемы остановки).

Для этого и многих связанных результатов, см. Также:

• Этот опрос от Gasarch

• Книга « Ограниченные запросы в теории рекурсии » Гасарха и Мартина.

РЕДАКТИРОВАТЬ: Аргумент, на который я ответил, не был неправильным, но он немного вводил в заблуждение, поскольку он только показал, что верхняя граница должна быть жесткой для некоторых $n$ (что на самом деле тривиально, так как оно должно быть жестким, когда $n=2$ и предел 1).

Вот более точный аргумент. Это показывает, что если верхняя граница$\log_2 n$ свободен для любого конкретного $n$тогда для всех $n$ необходимое количество оракулов $O(1)$,

(Конечно, это не $O(1)$так что верхняя граница никогда не бывает свободной! Но я на самом деле не доказываю это здесь, и, учитывая другой ответ на проблему, это не стоит того, чтобы ее преследовать.)

Рассмотрим проблему вычисления максимального выхода :

Учитывая $n$-кратного $(M_1,\ldots,M_n)$ машин Тьюринга, вычислите максимальную производительность (машин Тьюринга, которые останавливаются, если работают на $\epsilon$). Если ни один из них не остановится, верните 0.

Как функция $n$наихудшее число вызовов оракула, необходимое для вычисления этой функции, совпадает с числом, необходимым для определения, какой из $n$заданные машины останавливаются. (Если я знаю, какие машины останавливаются, я могу легко вычислить максимальную производительность. И наоборот, если я хочу знать, какие машины останавливаются, следуя конструкции в формулировке задачи, я могу построить машины$\{M'_i\}$ $(i=1,2,\ldots,n)$ где $M'_i$ работает все $n$ отдавая машины параллельно, затем останавливается и выводится $i$ если $i$из них когда-либо останавливаются. Максимальный выходной скажет мне число, которое останавливается. Исходя из этого, я могу точно рассчитать, какая остановка.)

Теперь пусть $n_0$ быть наименьшим целым $n$ (если есть) так, чтобы выполнялось следующее:

С помощью $C(n) = \max\{k \in \mathbb{Z} : 2^k < n\}$ оракулов, можно вычислить максимальный выход $n$данные машины. (То есть верхняя граница не является жесткой для$n$.)

очевидно $n_0>1$, потому что $C(1) = -1$, По факту,$n_0>2$ Также из-за $C(2) = 0$, но неразрешимо вычислить максимальный выход $2$данные машины (без оракулов). Теперь рассмотрим больше$n$:

Претензия: если$n_0$ конечно, то для любого $n$можно рассчитать максимальный выход $n$ данные машины в $C(n_0)$оракулы (Обратите внимание, что если$n_0$ конечно, то $C(n_0) = O(1)$.)

Доказательство. , Докажем это индукцией по$n$, Базовые случаи$n\le n_0$, которые держатся по определению $n_0$ а также $C$,

Позволять $Q_0$ быть ТМ, который, учитывая любой $n_0$ Машины Тьюринга, вычисляет максимальную производительность, используя только $C(n_0)$ призывает к оракулу.

Исправить любой $n>n_0$, Учитывая любой$n$ машины $M_1,\ldots, M_n$, рассчитайте максимальную мощность следующим образом.

Сосредоточиться на первом $M_1,\ldots,M_{n_0}$машины. Рассмотрим бег$Q_0$ на этих $n_0$машины. Обратите внимание, что$Q_0$ марки $C(n_0)$ призывает к оракулу, а есть только $n' = 2^{C(n_0)}$возможные ответы оракула на эти звонки. Обратите внимание, что по определению$n' = 2^{C(n_0)} < n_0$, Позволять$o_i$ обозначить $i$й возможный ответ. Для каждого$i=1,\ldots,n'$, построить машину $M'_i$ что имитирует $Q_0$ на этих машинах так:

TM $M'_i$ (на входе $\epsilon$):

1. Имитировать $Q_0$ на $n_0$ машины $(M_1,\ldots,M_{n_0})$, но вместо того, чтобы называть оракула, предположим, что оракул отвечает согласно $o_i$,
2. Это моделирование может не остановиться (например, если $o_i$ это не то, что на самом деле вернул бы оракул).
3. Если симуляция останавливается, пусть $h_i$ быть максимальным выходом, который $Q_0$ говорит будет дано.
4. Ласточкин хвост все $n_0$ машины $(M_1,\ldots,M_{n_0})$, Если один из них когда-либо выводит$h_i$, остановка и вывод $h_i$,

Теперь в данной последовательности $n$ машины, замени первый $n_0$ машины $M_1,\ldots,M_{n_0}$ этими $n'< n_0$ машины $M'_1,\ldots,M'_{n'}$, Вернуть значение, вычисленное путем повторения в этой последовательности$n-(n_0-n') < n$машины. (Обратите внимание, что оракул не вызывается до повторного использования, поэтому оракул вызывается только после достижения базового варианта.)

Вот почему это вычисление верно. Для$i$ такой, что $o_i$ «правильный» ответ оракула $Q_0$ на запросы, $M'_i$ остановится и даст правильный максимальный выход оригинала $n_0$машины. Таким образом, максимальный выход$n'$ машины $(M'_1,\ldots,M'_{n'})$ по крайней мере, максимальный выход $n_0$ машины $(M_1,\ldots,M_{n_0})$, С другой стороны, к шагу 4 нет$M'_i$ может дать вывод, который больше, чем максимальный выход $(M_1,\ldots,M_{n_0})$, Таким образом, максимальный выход$n'$ машины $(M'_1,\ldots,M'_{n'})$ равно максимальному выходу $n_0$машины, которые они заменяют. QED