Gerador de números verdadeiramente aleatório: Turing computável?

39

Estou procurando uma resposta definitiva para saber se a geração de números "verdadeiramente aleatórios" é computável por Turing. Não sei como expressar isso com precisão. Esta pergunta do StackExchange sobre "algoritmos eficientes para geração de números aleatórios" chega perto de responder à minha pergunta. Charles Stewart diz em sua resposta: "Não é possível gerar [aleatoriedade de Martin-Löf] por uma máquina". Ross Snider diz que "qualquer processo determinístico (como a Turing / Register Machines) não pode produzir números aleatórios 'filosóficos' ou 'verdadeiros'". Existe uma noção clara e aceita do que constitui um gerador de números verdadeiramente aleatório? E se sim, sabe-se que não pode ser calculado por uma máquina de Turing?

Talvez me apontar a literatura relevante seja suficiente. Obrigado por qualquer ajuda que você pode fornecer!

Editar. Agradecemos a Ian e Aaron pelas respostas bem informadas! Sou relativamente sem escolaridade nesta área e sou grato pela assistência. Se eu puder estender um pouco a questão neste adendo: será que uma MT com acesso a uma fonte pura de aleatoriedade (um oráculo?) Pode calcular uma função que uma MT clássica não pode?

Joseph O'Rourke
fonte
1
Ajuda se você considerar a definição de "verdadeiramente aleatório" primeiro.
MS Dousti 13/09/10

Respostas:

52

Estou entrando na discussão bastante tarde, mas tentarei abordar várias perguntas que foram feitas anteriormente.

Primeiro, como observado por Aaron Sterling, é importante decidir primeiro o que queremos dizer com números "verdadeiramente aleatórios", e especialmente se estivermos analisando as coisas da perspectiva da complexidade computacional ou da computabilidade.

Permitam-me, no entanto, argumentar que, na teoria da complexidade, as pessoas estão interessadas principalmente em pseudo- aleatoriedade e geradores pseudo- aleatórios, ou seja, funções de cadeias para cadeias, de modo que a distribuição das seqüências de saída não possa ser diferenciada da distribuição uniforme por algum processo eficiente (onde vários significados de eficiente podem ser considerados, por exemplo, computadores com policitem, circuitos de tamanho polinomial etc.). É uma área de pesquisa bonita e muito ativa, mas acho que a maioria das pessoas concorda que os objetos que estuda não são verdadeiramente aleatórios, basta que pareçam aleatórios (daí o termo "pseudo").

Na teoria da computabilidade, surgiu um consenso sobre o que deveria ser uma boa noção de "aleatoriedade verdadeira", e é de fato a noção de aleatoriedade de Martin-Löf que prevaleceu (outras foram propostas e são interessantes de estudar, mas não revelam tudo). as boas propriedades que a aleatoriedade de Martin-Löf possui). Para simplificar, consideraremos a aleatoriedade para infinitas seqüências binárias (outros objetos, como funções de cadeias de caracteres para cadeias de caracteres, podem ser facilmente codificados por essa sequência).

Uma sequência binária infinita é aleatória de Martin-Löf se nenhum processo computável (mesmo que permitamos que esse processo seja computável em tempo exponencial triplo ou superior) possa detectar uma falha de aleatoriedade.α

(1) O que queremos dizer com "falha de aleatoriedade"? Essa parte é fácil: é um conjunto de medida 0, ou seja, uma propriedade que quase todas as seqüências não têm (aqui falamos de Lebesgue medir ou seja, a medida em que cada bit tem um probabilidade de ser 0 independentemente de todos os outros bits). Um exemplo dessa falha é "ter 1/3 de zeros assintoticamente e 2/3 de zeros", o que viola a lei de grandes números. Outro exemplo é "para cada n, os primeiros 2n bits de α estão perfeitamente distribuídos (tantos zeros quanto um)". Nesse caso, a lei dos grandes números é saturada, mas não o teorema do limite central. Etc etc.1/20α
(2) Como um processo computável pode testar se uma sequência não pertence a um conjunto específico de medida 0? Em outras palavras, quais conjuntos de medidas 0 podem ser descritos computacionalmente? É exatamente disso que se trata os testes de Martin-Löf. Um teste de Martin-Löf é um procedimento computável que, dada uma entrada k, computável (isto é, através de uma máquina de Turing com entrada ) gera uma sequência de cadeias w k , 0 , w k , 1 , ... de modo que o conjunto U k de sequências infinitas começando por uma daquelas w k , i tem uma medida no máximo 2 - kkwk,0wk,1Ukwk,i2k(se você gosta de topologia, observe que este é um conjunto aberto na topologia do produto para o conjunto de infinitas seqüências binárias). Então o conjunto tem a medida 0 e é referido como Martin-Löf nullset . Agora podemos definir a aleatoriedade de Martin-Löf dizendo que uma sequência binária infinita α é aleatória de Martin-Löf se não pertencer a nenhum conjunto nulo de Martin-Löf . G=kUk0α

Essa definição pode parecer técnica, mas é amplamente aceita como correta por várias razões:

  • é eficaz o suficiente, ou seja, sua definição envolve processos computáveis
  • é suficientemente forte: qualquer propriedade "quase certa" que você possa encontrar em um livro de teoria das probabilidades (lei dos grandes números, lei do logaritmo iterado etc.) pode ser testada por um teste de Martin-Löf (embora isso às vezes seja difícil de provar)
  • foi proposto independentemente por várias pessoas usando definições diferentes (em particular a definição de Levin-Chaitin usando a complexidade de Kolmogorov); e o fato de todos eles levarem ao mesmo conceito é uma dica de que deve ser a noção correta (um pouco como a noção de função computável, que pode ser definida através de máquinas de Turing, funções recursivas, cálculo lambda etc.)
  • a teoria matemática por trás disso é muito legal! veja os três excelentes livros Introdução à complexidade de Kolmogorov e suas aplicações (Li e Vitanyi), aleatoriedade e complexidade algorítmica (Downey e Hirschfeldt) Computabilidade e aleatoriedade (Nies).

Como é uma sequência aleatória de Martin-Löf? Bem, pegue uma moeda perfeitamente equilibrada e comece a jogá-la. Em cada flip, escreva um 0 para cara e 1 para coroa. Continue até o final dos tempos. É assim que uma sequência de Martin-Löf se parece :-)

Agora voltando à pergunta inicial: existe uma maneira computável de gerar uma sequência aleatória de Martin-Löf? Intuitivamente, a resposta deve ser NÃO , porque se podemos usar um processo computável para gerar uma sequência , certamente podemos usar um processo computável para descrever o singleton { α }, para que α não seja aleatório. Formalmente, isso é feito da seguinte maneira. Suponha que uma sequência α seja computável. Considere o seguinte teste de Martin-Löf: para todo k , basta gerar o prefixo a k de α de comprimento k , e nada mais. Isso tem uma medida no máximo (de fato, exatamente) 2 - kααααkakαk2k, e a interseção dos conjuntos como na definição, é exatamente { α }. QED !!Ukα

De fato, uma sequência aleatória Martin-Löf é incomputável em um sentido muito mais forte: se alguma computação do oráculo com o oráculo β (que por si só é uma sequência binária infinita) pode calcular α , então para todos os n , n - O ( 1 ) bits de β são necessários para calcular os primeiros n bits de α (essa é de fato uma caracterização da aleatoriedade de Martin-Löf, que infelizmente raramente é declarada como na literatura).αβαnnO(1)βnα


Ok, agora a parte "editar" da pergunta de Joseph: Será que uma MT com acesso a uma fonte pura de aleatoriedade (um oráculo?), Pode calcular uma função que uma MT clássica não pode?

Do ponto de vista da computabilidade, a resposta é "sim e não". Se você tiver acesso a uma fonte aleatória como um oráculo (onde a saída é apresentada como uma sequência binária infinita), com probabilidade 1, você obterá um oráculo aleatório de Martin-Löf e, como vimos anteriormente, o acaso de Martin-Löf implica não computável, portanto basta produzir o próprio oráculo! Ou, se você quiser uma função , considere a função f que, para todos os n, indica quantos zeros existem entre os primeiros n bits do seu oráculo. Se o oráculo for aleatório de Martin-Löf, essa função será não computável.f:NNfnn

Mas é claro que você pode argumentar que isso é trapaça: de fato, para um oráculo diferente, podemos ter uma função diferente, portanto há um problema de não reprodutibilidade. Portanto, outra maneira de entender sua pergunta é a seguinte: existe uma função que não é computável, mas que pode ser "computada com probabilidade positiva", no sentido de que existe uma máquina de Turing com acesso a um oráculo aleatório que, com probabilidade positiva (sobre o oráculo), calcula f . A resposta é não, devido a um teorema de Sacks cuja prova é bastante simples. Na verdade, ele foi respondido principalmente por Robin Kothari: se a probabilidade de a MT estar correta é maior que 1/2, é possível procurar todos os n em todos os cálculos possíveis do oracle com a entrada nffnne encontre a saída que obtém o "voto majoritário", isto é, que é produzido por um conjunto de oráculos de medida acima de 1/2 (isso pode ser feito de maneira eficaz). O argumento se estende até probabilidades menores: suponha que a TM produza com probabilidade ϵ > 0 . Pelo teorema da densidade de Lebesgue, existe uma cadeia finita σ tal que, se fixarmos os primeiros bits do oráculo como exatamente σ , e depois pegarmos os outros bits aleatoriamente, calcularemos f com probabilidade de pelo menos 0,99. Tomando tal σ , podemos aplicar o argumento acima novamente.fϵ>0σσfσ

LaurentBienvenu
fonte
8
que resposta linda.
Suresh Venkat
1
Aprecio muito a clareza da sua resposta detalhada a esta (e para mim!) Pergunta emaranhada. Obrigado!
Joseph O'Rourke
12

Existe (talvez) uma distinção a ser feita entre "Turing computável" e "efetivamente computável" para responder à sua pergunta. Se se define "processo aleatório" como "um processo que não pode ser previsto, independentemente dos recursos que temos", e se define "processo determinístico" como "processo previsível, dada a entrada e o acesso a (talvez muitos) recursos, "então nenhuma função computável de Turing pode ser aleatória, porque se conhecêssemos a máquina de Turing e a simulássemos, sempre poderíamos prever o resultado do próximo" experimento "do processo.

Nesta estrutura, um teste de Martin-Lof pode ser visto como um processo determinístico, e a definição de uma sequência aleatória é precisamente uma sequência cujo comportamento não é previsto por nenhum processo de Martin-Lof / processo computacional / determinístico de Turing.

Isso, no entanto, levanta a questão: "Uma sequência aleatória é efetivamente calculável na vida real?" De fato, existe uma indústria aqui. Existem CDs publicados com bilhões de bits aleatórios (?) Neles usados ​​para realizar simulações de sistemas físicos por computador, etc. Esses CDs garantem que suas sequências de bits passem por vários testes de Martin-Lof. O livro The Drunkard's Walk: How Randomness Rules Our Lives fornece uma explicação pop-sci dessa questão, em mais detalhes.

Ponto irrelevante: Gosto da sua coluna. :-)

Aaron Sterling
fonte
11

Intuitivamente, "aleatório" significa "imprevisível", e qualquer sequência gerada por uma máquina de Turing pode ser prevista executando a máquina, portanto, as máquinas de Turing não podem produzir números "verdadeiramente aleatórios". Existem várias definições formais de seqüências aleatórias (aleatoriedade só faz sentido quando o comprimento de uma cadeia vai para o infinito), todas essencialmente equivalentes. Talvez o mais natural deles seja a aleatoriedade de Martin-Lof, o que significa que uma sequência passa em todos os testes estatísticos computáveis ​​possíveis para estocástica e o aleatório de Chaitin, o que significa que todas as subsequências iniciais são incompressíveis (mais especificamente, têm alta complexidade de Kolmogorov). Em ambas as definições, é incomputável gerar seqüências aleatórias e reconhecê-las. Veja o livro "Informação e aleatoriedade:

Ian
fonte
Link para livro aqui: amazon.com/…
Suresh Venkat
Obrigado, Ian & Suresh, estou recuperando esse livro da nossa biblioteca!
Joseph O'Rourke
Outro grande livro é "Computability and randomness", de Nies.
Diego de Estrada
11

Qualquer um que considere métodos aritméticos de produzir dígitos aleatórios está, é claro, em um estado de pecado. Pois, como foi apontado várias vezes, não existe um número aleatório - existem apenas métodos para produzir números aleatórios, e um procedimento aritmético rigoroso, é claro, não é esse método. - John von Neumann

Jeffε
fonte
Ha! Ótimas citações, Jeff! E com um ponto substantivo.
Joseph O'Rourke
7

Parece que ninguém respondeu ao seu adendo, então vou tentar:

Se eu puder estender um pouco a questão neste adendo: será que uma MT com acesso a uma fonte pura de aleatoriedade (um oráculo?) Pode calcular uma função que uma MT clássica não pode?

Vou tentar tornar a pergunta mais precisa e depois respondê-la. Porém, minha versão pode não ser o que você tinha em mente, então, deixe-me saber se não é.

Temos uma TM determinística com acesso a um gerador de números aleatórios. Esta TM agora calcula alguma função (uma função real, isto é, um mapa determinístico de um espaço de entrada para um espaço de saída), utilizando o gerador de números aleatórios de alguma maneira.

Então, a TM com acesso à aleatoriedade pode cometer erros? Caso contrário, o DTM deve fornecer a resposta correta, independentemente de quais bits aleatórios foram fornecidos. Nesse caso, os bits aleatórios são desnecessários, pois você pode considerar que a string aleatória seja 00000 ...

fi(x,r)fir

Robin Kothari
fonte
Acho isso interessante: "Se não, o DTM deve dar a resposta correta, independentemente de quais bits aleatórios foram fornecidos". Obrigado!
Joseph O'Rourke
Na verdade, eu não entendo isso. Você parece sugerir que P = ZPP ou que um algoritmo aleatório com erro zero (por exemplo, um algoritmo de Las Vegas) deve ser determinístico?
Suresh Venkat
Por um DTM com acesso da Oracle a decidir um idioma, presumi que o DTM parasse após um período finito de tempo. Nesse caso, podemos nos livrar do oráculo. Para erro zero, basta substituí-lo por 0000 ... e, para qualquer outro propósito, pode-se aplicar força bruta em todas as seqüências aleatórias de comprimento finito. (Eu tenho certeza que alguém provavelmente tem a opinião de que os algoritmos de Las Vegas não são realmente algoritmos, uma vez que não necessariamente terminam.)
Robin Kothari
5

Em relação à sua "questão de edição": faz uma grande diferença se você está perguntando sobre computabilidade ou complexidade. Se houver limites de complexidade na TM, você obtém o chamado modelo de oráculo aleatório . Se a TM pode usar recursos arbitrariamente grandes, mas finitos, você está no mundo da aleatoriedade relativa : existem hierarquias de aleatoriedade dos oráculos, assim como existem graus de Turing. (Ponto de vista: uma das (in) famosas críticas de Koblitz e Menzes foi sobre o uso do modelo aleatório de oráculo, então sua meta-pergunta está tocando nos recentes debates acadêmicos.)

Aaron Sterling
fonte
Apenas para esclarecer: Joe queria um oráculo aleatório (que é essencialmente uma função hash aleatória) ou apenas uma fonte de aleatoriedade? estas não são a mesma coisa, são?
Suresh Venkat
Obrigado, Aaron, a menção das hierarquias aleatórias do oráculo é útil.
Joseph O'Rourke
@ Suresh: eu quis dizer uma fonte de aleatoriedade.
Joseph O'Rourke
Vocês provavelmente estão muito à minha frente aqui, mas eu estava tentando dizer que a aleatoriedade precisa ser definida em relação a um "quadro de referência", isto é, os recursos disponíveis para fazer previsões. Uma "fonte de aleatoriedade" pode ser aleatória com relação a uma máquina de Turing, mas não com relação ao Oracle Halting. Eu concordo com a resposta de Robin Kothari; meu argumento era apenas que uma "fonte pura de aleatoriedade" parece não existir nas definições atuais, porque sempre poderíamos diagonalizar contra ela e obter algo aleatoriamente.
Aaron Sterling
5

Ainda estou tentando entender sua pergunta modificada, especialmente o que você limita na TM. Portanto, embora essa resposta possa não atingir exatamente o que você deseja, talvez ajude a restringir um pouco as coisas.

Sabemos que existe um resultado de impossibilidade incondicional para aproximar com um fator subexponencial o volume de um corpo convexo deterministicamente (este é um resultado antigo de Bárány e Füredi ). Por outro lado, podemos obter um FPRAS para esse problema usando amostragem. Este é um exemplo da separação que você está procurando?

Suresh Venkat
fonte
Esse resultado é para algoritmos de tempo polinomial, certo? Eu interpretei a pergunta do OP como uma sobre teoria da computabilidade, não teoria da complexidade. Com o que quero dizer, eu interpretei "O conjunto de problemas resolvidos por uma fonte aleatória de DTM + é maior do que os resolvidos por um DTM?"
Robin Kothari
isso é possível. Daí a minha tentativa de realizá-lo com mais detalhes. No nível da computabilidade, uma discrepância para mim invalidaria a tese de Church-Turing.
Suresh Venkat
Eu gosto desse exemplo de volume! Embora tenha perguntado especificamente sobre a teoria da computabilidade, também estou interessado em diferenças de complexidade. Não vejo como isso poderia invalidar a TC, porque as respostas anteriores estabeleceram que uma fonte pura de verdadeira aleatoriedade não é computável ...?
Joseph O'Rourke
Acho que depois de formalizar o que queremos dizer com DTM com acesso a uma fonte de aleatoriedade (com seus critérios de aceitação, probabilidade de interrupção etc.), poderemos mostrar que esse modelo também calcula exatamente as linguagens recursivas.
Robin Kothari
Verdadeiro (no domínio comutável). Mas agora eu me pergunto: suponha que construamos uma string cujo bit i é o resultado da execução da i-máquina turing em uma codificação própria. Ser capaz de prever essa string corresponderia à solução do problema de Halting, e essa string é aleatória no sentido de Martin-Lof?
Suresh Venkat