Limite inferior do número de chamadas do oracle para resolver instâncias do problema de parada

Encontrei a seguinte pergunta, que é um exercício fácil (spoiler abaixo).

Recebemos instâncias do problema de interrupção (ou seja, TMs ) e precisamos decidir exatamente quais delas serão interrompidas no . Ou seja, precisamos . Recebemos um oráculo para o problema de parada, mas temos que usá-lo um número mínimo de vezes.$n$$M_1,...,M_n$$\epsilon$$\{i: M_i\text{ halts on }\epsilon\}$

Não é difícil mostrar que isso pode ser feito com .$\log (n+1)$

Minha pergunta é: podemos provar um limite inferior? Há motivos para suspeitar que esse limite será muito difícil de encontrar?

A resposta para a pergunta em si (spoiler, mouse suspenso):

Considere o caso de TMs. Podemos construir um TM que executa em paralelo e pára se pelo menos dois deles pararem (caso contrário, ele ficará preso). Da mesma forma, podemos construir uma TM que pare se pelo menos um deles parar. Podemos então chamar o oráculo em . Se parar, podemos executar as máquinas em paralelo e esperar que uma pare. Podemos então chamar o oráculo no último. Se o oráculo disser "não", executamos o oráculo em . Se parar, executamos as máquinas até uma parar, e é a única que pára. Se não parar, nenhum deles será interrompido. Estender isso para máquinas é fácil.H 2 M 1 , M 2 , M 3 H 1 H 2 H 1 H 1$3$$H_2$$M_1,M_2,M_3$$H_1$$H_2$$H_1$$H_1$$n$

A primeira observação sobre essa questão é que parece impossível resolver usando ferramentas teóricas da informação, uma vez que confiamos crucialmente em nossa capacidade de obter informações executando as máquinas sem o oráculo.

O resultado pode ser encontrado em

• Beigel, R., Gasarch, WI, Gill, J. e Owings, J. Terse, conjuntos de superterse e detalhado . Informar. e Comput. 103 (1993), n. 1, 68-85.

A prova deles mostra, de fato, que seu problema não pode ser resolvido com menos de consultas a qualquer conjunto X , sem falar no próprio problema de parada. Para algumas notações, seu problema às vezes é indicado como C K n ou C H A L T n (dependendo da sua notação favorita para o problema de parada).$\log_2 n$$X$$C_n^K$$C_n^{HALT}$

Para este e muitos resultados relacionados, consulte também:

• Esta pesquisa da Gasarch

• O livro Consultas vinculadas à teoria da recursão de Gasarch e Martin.

EDIT: O argumento com o qual eu respondi não estava errado, mas era um pouco enganador, pois mostrava apenas que o limite superior precisava ser apertado para alguns (o que é realmente trivial, pois precisa ser apertado quando n = 2 e o limite é 1).$n$$n=2$

Aqui está um argumento mais preciso. Isso mostra que, se o limite superior do estiver frouxo para qualquer n específico , para todos os n, o número de chamadas oracle necessárias será O ( 1 $\log_2 n$$n$ $n$$O(1)$ .

(Com certeza, é não $O(1)$ , de modo que o limite superior é nunca solta! Mas eu realmente não provar que aqui, e dada a outra resposta para o problema, não parece vale a pena perseguir.)

Considere o problema de calcular a saída máxima :

Dado um duplo ( M 1 , … , M n ) de máquinas de Turing, calcule a saída máxima (das máquinas de Turing que param, se executadas em ϵ ). Se nenhum deles parar, retorne 0.$n$$(M_1,\ldots,M_n)$$\epsilon$

Em função de , o pior número de chamadas oracle necessárias para calcular essa função é o mesmo que o número necessário para decidir qual das n máquinas determinadas será interrompida. (Se eu souber quais máquinas param, posso calcular facilmente a produção máxima. Por outro lado, se eu quiser saber quais máquinas param, seguindo a construção na declaração do problema, posso construir máquinas { M ′ i } ( i = 1 , 2 , … , N ) onde M ′ i executa todas as n máquinas dadas em paralelo, então pára e produz $n$$n$$\{M'_i\}$ $(i=1,2,\ldots,n)$$M'_i$$n$$i$se algum dia paro. A saída máxima me dirá o número que será interrompido. Daí eu posso calcular exatamente qual parada.)$i$

Agora, vamos ser o número inteiro menor n (se houver) de tal forma que mantém o seguinte:$n_0$$n$

Usando chamadas Oracle, pode-se calcular a saída máxima de n máquinas dadas. (Ou seja, o limite superior não é apertado para n .)$C(n) = \max\{k \in \mathbb{Z} : 2^k < n\}$$n$$n$

Claramente , porque C ( 1 ) = - 1 . De fato, n 0 > 2 também, porque C ( 2 ) = 0 , mas é indecidível calcular a saída máxima de 2 máquinas fornecidas (sem chamadas de oracle). Agora considere n maior :$n_0>1$$C(1) = -1$$n_0>2$$C(2) = 0$$2$$n$

Reivindicação: Se for finito, então, para qualquer n , pode-se calcular a saída máxima de n máquinas dadas em C ( n 0 ) chamadas oracle. $n_0$$n$$n$$C(n_0)$(Observe que se for finito, então C ( n 0 ) = O ( 1 ) .)$n_0$$C(n_0) = O(1)$

Prova. . Provamos isso por indução em . Os casos base são n ≤ n 0 , o qual, por definição, conter de n 0 e C .$n$$n\le n_0$$n_0$$C$

Seja a MT que, dadas quaisquer n 0 máquinas de Turing, calcula a saída máxima usando apenas chamadas C ( n 0 ) para o oráculo.$Q_0$$n_0$$C(n_0)$

Corrija qualquer . Dadas as n máquinas M 1 , … , M n , calcule a saída máxima da seguinte maneira.$n>n_0$$n$$M_1,\ldots, M_n$

Concentre-se nas primeiras máquinas . Considere executar Q 0 nessas n 0 máquinas. Observe que Q 0 faz chamadas C ( n 0 ) ao oráculo, e há apenas n ′ = 2 C ( n 0 ) respostas possíveis pelo oráculo para essas chamadas. Observe que, por definição n ′ = 2 C ( n 0 ) < 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$. Deixe denotar o i th resposta possível. Para cada i = 1 , ... , n ' , construir uma máquina M ' i que simula Q 0 nessas máquinas, como segue:$o_i$$i$$i=1,\ldots,n'$$M'_i$$Q_0$

TM (na entrada ϵ ):$M'_i$$\epsilon$

1. Simular sobre os n 0 máquinas ( M 1 , ... , M n 0 ) , mas em vez de chamar o oráculo, assumir as responde oracle de acordo com o i .$Q_0$$n_0$$(M_1,\ldots,M_{n_0})$$o_i$
2. Esta simulação pode não parar (por exemplo, se não é o que o oráculo seria realmente voltar).$o_i$
3. Se as paradas de simulação, vamos ser a potência máxima que Q 0 diz que seria dado.$h_i$$Q_0$
4. Detalhe todas as máquinas ( M 1 , … , M n 0 ) . Se um deles alguma vez der saída h i , pare e dê saída h i .$n_0$$(M_1,\ldots,M_{n_0})$$h_i$$h_i$

Agora, na seqüência dada de máquinas, substitua as primeiras n 0 máquinas M 1 , … , M n 0 por essas n ′ < n 0 máquinas M ′ 1 , … , M ′ n ' . Retorne o valor calculado recorrendo nesta sequência de n - ( n 0 - n ′ ) < $n$$n_0$$M_1,\ldots,M_{n_0}$$n'< n_0$$M'_1,\ldots,M'_{n'}$$n-(n_0-n') < n$máquinas (Observe que o oráculo não é chamado antes da recorrência, de modo que o oráculo é chamado somente quando o caso base é atingido.)

Aqui está o porquê dessa computação estar correta. Para o de modo a que o i é a `` correcto '' resposta pelo oráculo Q 0 para as consultas, H ' i pararia e dar a saída máxima correcta do original n 0 máquinas. Assim, a produção máxima das n ′ máquinas ( M ′ 1 , … , M ′ n ′ ) é pelo menos a produção máxima das n 0 máquinas ( M 1 , … $i$$o_i$$Q_0$$M'_i$$n_0$$n'$$(M'_1,\ldots,M'_{n'})$$n_0$ . Por outro lado, na etapa 4, nenhum M ′ i pode fornecer uma saída maior que a saída máxima de ( M 1 , … , M n 0 ) . Assim, a produção máxima das n ′ máquinas ( M ′ 1 , … , M ′ n ′ ) é igual à produção máxima das n 0 máquinas que elas substituem. QED$(M_1,\ldots,M_{n_0})$$M'_i$$(M_1,\ldots,M_{n_0})$$n'$$(M'_1,\ldots,M'_{n'})$$n_0$