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

9

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.nM1,...,Mnϵ{i:Mi halts on ϵ}

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 n3H2M1,M2,M3H1H2H1H1n

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.

Shaull
fonte
@ Kaveh - como Neal Young escreveu, precisamos calcular o conjunto exato de máquinas de parada.
Shaull 19/03/2013

Respostas:

11

O resultado pode ser encontrado em

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).log2nXCnKCnHALT

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

Joshua Grochow
fonte
10

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).nn=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 )registro2nn nO(1 1) .

(Com certeza, é não O(1 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(M1 1,...,Mn)ϵ

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 inn{MEu} (Eu=1 1,2,...,n)MEunEuse algum dia paro. A saída máxima me dirá o número que será interrompido. Daí eu posso calcular exatamente qual parada.)Eu

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

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{kZ:2k<n}nn

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 :n0 0>1 1C(1)=1n0>2C(2)=02n

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. n0nnC(n0)(Observe que se for finito, então C ( n 0 ) = O ( 1 ) .)n0C(n0)=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 .nnn0n0C

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.Q0n0C(n0)

Corrija qualquer . Dadas as n máquinas M 1 , , M n , calcule a saída máxima da seguinte maneira.n>n0nM1,,Mn

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 0M1,,Mn0Q0n0Q0C(n0)n=2C(n0)n=2C(n0)<n0. 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:oiii=1,,nMiQ0

TM (na entrada ϵ ):Miϵ

  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 .Q0n0(M1,,Mn0)oi
  2. Esta simulação pode não parar (por exemplo, se não é o que o oráculo seria realmente voltar).oi
  3. Se as paradas de simulação, vamos ser a potência máxima que Q 0 diz que seria dado.hiQ0
  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 .n0(M1,,Mn0)hihi

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 ) < nnn0M1,,Mn0n<n0M1,,Mnn(n0n)<nmá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 , ,ioiQ0Min0n(M1,,Mn)n0 . 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(M1,,Mn0)Mi(M1,,Mn0)n(M1,,Mn)n0

Neal Young
fonte