Uma máquina de Turing probabilística pode resolver o problema da parada?

29

Um computador que recebe um fluxo infinito de bits verdadeiramente aleatórios é mais poderoso que um computador sem um. A questão é: ela é poderosa o suficiente para resolver o problema da parada?

Ou seja, um computador probabilístico pode determinar se um programa determinístico é interrompido ou não ?

Exemplo de um computador probabilístico que faz algo que um determinista não pode: Considere um programa pequeno (com menos de um kilobyte de comprimento) que produz uma string com complexidade de Kolmogorov maior que um gigabyte. A complexidade de Kolmogorovde uma sequência é o comprimento do programa determinístico mais curto que produz essa sequência. Assim, por definição, um programa determinístico não pode produzir uma cadeia cuja complexidade seja maior que seu próprio comprimento. No entanto, se um fluxo infinito de bits verdadeiramente aleatórios é fornecido, um pequeno programa é capaz de realizar a tarefa com 99.99999 ...% de sucesso simplesmente ecoando, digamos, 10 bilhões de bits aleatórios e esperando que a complexidade Kolmogorov desses bits seja alta o suficiente . Portanto, produzir uma série de complexidade superior de Kolmogorov está dentro do horizonte de possibilidades do programa probabilístico, mas não é possível para o programa determinístico.

Dito isto, estou me perguntando se é possível usar bits verdadeiramente aleatórios para cortar a serra no problema de parada. Por exemplo, um algoritmo pode gerar aleatoriamente teoremas e provar / refutar / descartá-los até que saiba o suficiente para provar / refutar que um determinado programa determinístico é interrompido.

Joey Adams
fonte
3
@ downvoter: Isso não deveria ter recebido um voto negativo sem um comentário.
Dave Clarke
3
O que impede uma TM determinística de enumerar todos os casos? Aqui, a verificação de um palpite é o problema, não o próprio palpite. Observe também que você não pode realmente dizer que é estritamente mais poderoso se criar o resultado desejado apenas com uma probabilidade . p<1
Raphael
11
"um programa determinístico não pode produzir uma cadeia cuja complexidade seja maior que seu próprio comprimento." Basta que outra máquina determinística produza a mesma saída. Observe que as MTs determinísticas podem simular não apenas as probabilísticas, mas também as MTs não determinísticas (com número arbitrário de alternâncias).
Kaveh
Ontem eu estava prestes a dizer - olhando para Kaveh et al - que era uma pergunta muito básica para este site (a mesma pergunta para o NTM é um resultado básico em todos os primeiros cursos de teoria). Dado que foi necessário um grande esforço para formalizar a "MT probabilística", fico feliz por não ter feito.
Raphael
11
E veja as respostas esclarecendo a minha pergunta anterior relacionada TCS: cstheory.stackexchange.com/questions/1263/...
Joseph O'Rourke

Respostas:

22

edit: Acabei de perceber que algumas das coisas que escrevi eram totalmente sem sentido, desculpe por isso. Agora mudei a prova e fiz a definição de máquina probabilística que estou usando mais precisa.

Não sei se entendi corretamente sua definição de máquina probabilística de Turing: é uma máquina com uma fita adicional na qual uma seqüência infinita incompressível é escrita e, além disso, age como uma máquina determinística? Se corrigirmos a string incompressível, a classe que obtemos não parece ser interessante.

Acho que podemos definir uma máquina de Turing probabilística de várias maneiras. Usarei uma definição que parece bastante natural (e para a qual minha prova funciona;) Vamos definir uma máquina probabilística assim: ela recebe uma fita adicional na qual uma string infinita é escrita, dizemos que essa máquina decide uma linguagem se for cada x L pára e aceita com probabilidade > 1LxL , quando a probabilidade é assumida sobre essas seqüências aleatórias adicionais e para cadaxL,ele para e rejeita com probabilidade>1>12xL .>12

Agora mostraremos que, se existe uma máquina probabilística que resolve o problema de parada para as máquinas determinísticas, poderíamos usá-la para construir uma máquina determinística H que resolve o problema de parada para as máquinas determinísticas - e sabemos que essa máquina não pode existir.PH

Suponha que exista. Podemos construir uma máquina determinística M que toma como entrada uma máquina probabilística R com alguma entrada x , quePMRx

  • interrompe e aceita se e somente se aceita x (ou seja, R interrompe e aceita x em mais da metade das seqüências aleatórias).RxRx
  • interrompe e rejeita se e somente se rejeita x (ou seja, R interrompe e rejeita x em mais da metade das seqüências aleatórias).RxRx
  • loops caso contrário

Basicamente, vai para todos i 1 , 2 , . . . simular R na entrada x e em cada cadeia de caracteres a partir de 0 , 1 i como um prefixo da cadeia em R fita aleatório 's. Agora:Mi1,2,...Rx0,1iR

  • se for prefixos de comprimentoiRinterrompida e aceito sem tentar ler mais do queibits da fita aleatório,Mpára e aceita>12i RiM
  • se for prefixos de comprimentoiRparou e rejeitou sem tentar ler mais do queibits da fita aleatório,Mpára e rejeita>12i RiM
  • caso contrário, executa a simulação com i : = i + 1 .Mi:=i+1

Temos que nos convencer agora de que, se aceita (rejeita) x com probabilidade p > 1Rx , em seguida, para algunsique aceitará (rejeitar) para>1p>12i prefixos de comprimentoida cadeia aleatória, sem tentar ler mais do queibits da fita aleatória. É técnico, mas bastante fácil - se assumirmos o contrário, a probabilidade de aceitar (rejeitar) se aproxima dep>1>12ii comoivai para o infinito, portanto, para algunsiterá de serp>1p>12ii .p>12

Agora, apenas definimos nossa máquina determinística resolvendo o problema de parada (ou seja, decidindo se uma determinada máquina determinística N aceita uma determinada palavra x ) a como H ( N , x ) = M ( P ( N , x ) ) . Observe que M ( P ( N , x ) ) sempre pára, porque a decisão de um idioma por nossas máquinas probabilísticas foi definida de tal maneira que um desses dois sempre ocorre:HNxH(N,x)=M(P(N,x))M(P(N,x))

  • a máquina pára e aceita por mais da metade das seqüências aleatórias
  • a máquina pára e rejeita por mais da metade das seqüências aleatórias.
Karolina Sołtys
fonte
Obrigado por elaborar o meu comentário "apenas enumere"! ;) Dois comentários técnicos: No ponto um, você quer dizer ? No final, você quer dizer S ( Q ) ? >2i1S(Q)
Raphael
11
Observe que, se você não exige que P pare sempre, é trivial construir mesmo uma máquina de Turing determinística P que aceita se e somente se a determinada máquina de Turing determinística parar.
Tsuyoshi Ito
Qual é a sua suposição? Você não pode negar uma máquina de Turing probabilística, a menos que seja garantida a interrupção.
Tsuyoshi Ito
A probabilidade de parada é tomada sobre a sequência adicional E as palavras de entrada, ou o quê?
M. Alaggan
11
@ Mohamed ALAGGAN: Não, essa parte está correta como está escrito: a probabilidade é assumida apenas pela sequência adicional (especificando os resultados das jogadas da moeda). Como não estamos assumindo nenhuma distribuição de probabilidade na sequência de entrada, a probabilidade sobre a sequência de entrada não está bem definida. Mesmo que uma distribuição de probabilidade na sequência de entrada seja definida, a alta probabilidade de resposta correta sobre a sequência de entrada implica apenas que o algoritmo esteja correto para a maioria das entradas, o que é diferente do requisito usual em um algoritmo.
Tsuyoshi Ito
14

Depende do que você entende por algoritmo probabilístico, que determina algum predicado.

Existe um algoritmo probabilístico trivial P tal que, para uma máquina de Turing determinística M ,

  • P ( M ) aceita com probabilidade diferente de zero se M parar,
  • P ( M ) nunca aceita se M não parar, e
  • P ( H ) paradas com uma probabilidade para cada M .

Portanto, o algoritmo probabilístico P resolve o problema de parada para máquinas determinísticas de Turing nesse sentido. (Aqui " M pára" significa " M pára na entrada vazia".)

No entanto, se você reforçar o requisito de qualquer maneira sensata, é improvável que você possa resolver o problema de parada de máquinas determinísticas de Turing. Por exemplo,

  • Se você exige que P ( M ) pare sempre, em vez de apenas com probabilidade 1 , é claro que P pode ser simulado por um algoritmo determinístico. (Veja Wikipedia para uma explicação da diferença entre "sempre" e "com probabilidade 1.")
  • Se você restringir os limites de erro exigindo que P ( M ) pare e dê a resposta certa com probabilidade estritamente maior que 1/2 para cada M (ou seja, você não se importa se P ( M ) não parar ou parar e dar a resposta errada no restante dos casos), então P pode ser simulado por um algoritmo determinístico, usando o argumento indicado na resposta de Karolina Sołtys .

Portanto, um algoritmo probabilístico não pode resolver o problema de parada de máquinas determinísticas de Turing nesses sentidos.

Tsuyoshi Ito
fonte
Perdoe minha ignorância, mas qual é a diferença entre parar '' sempre '' e parar '' com probabilidade 1 ''?
Rob Simmons
11
@ Rob: Eu acho que é um ponto complicado. Considere uma simples máquina probabilística de Turing que apenas joga uma moeda repetidamente até que o resultado seja o cara. Esta máquina de Turing pára, exceto quando todas as moedas lançadas resultam nas caudas. Portanto, ele pára com a probabilidade 1, mas nem sempre pára.
Tsuyoshi Ito
Encontrei uma explicação da diferença entre "sempre" e "com probabilidade 1" na Wikipedia e adicionei o mesmo link na resposta.
Tsuyoshi Ito
Se você permitir que P (M) falhe por não parar, não sei como você pode fazer uma simulação determinística. Por exemplo, suponha que você execute sua simulação determinística em algum conjunto de seqüências de prefixos comprimento-N e, após algum tempo, <50% dos prefixos pararam e deram uma resposta. Como você sabe se as seqüências de prefixos restantes simplesmente precisam de mais tempo para retornar uma resposta ou se estão todas presas em um loop infinito como parte da condição de falha? Se o primeiro, você continua a esperar. Neste último caso, você encerra a rodada atual e executa novamente em todos os prefixos de comprimento-N + 1.
Mike Battaglia
Mas isso é impossível de determinar, porque é o problema da parada! Não temos como saber se a máquina de Turing irá parar nessas entradas ou não.
Mike Battaglia
12

PPP

Eu acho que esse foi o significado do comentário de Raphael.

Marc
fonte
7

ANA

de Leeuw, K., Moore, EF, Shannon, CE e Shapiro, N. Computabilidade por máquinas probabilísticas, estudos de autômatos, pp. 183-212. Anais de estudos de matemática, no. 34. Princeton University Press, Princeton, NJ, 1956.

G. Sacos, Graus de Insolvibilidade, Princeton University Press, 1963.

Bjørn Kjos-Hanssen
fonte