User:Fc20/Sequência algorítmicamente aleatória

Intuitivamente, uma sequência algoritmicamente aleatória (ou sequência aleatória) é uma sequência infinita de dígitos binários que aparece aleatoriamente para qualquer algoritmo. A definição, não podem ser aplicada igualmente para as sequências em qualquer conjunto finito de caracteres, mas ingenuinamente aplicada na prática. Seqüências aleatórias são os principais objetos de estudo na teoria da informação algorítmica.

Como diferentes tipos de algoritmos são às vezes considerados, variando de algoritmos com limites específicos no seu tempo de execução para os algoritmos que podem fazer perguntas a um oráculo, há diferentes definições de aleatoriedade. O mais comum deles é conhecido é a definição de Martin-Löf, mas também existem formas mais fortes e mais fracas de aleatoriedade. O termo "aleatório" utilizado para se referir a uma sequência sem clarificação é geralmente considerado como significando "Martin-Löf aleatório" (definido a seguir).

Visto que seqüências infinitas de dígitos binários podem ser identificadas com números reais no intervalo unitário, sequências binárias aleatórias são frequentemente chamadas de números reais aleatórios. Além disso, sequências binárias infinitas correspondem às funções características de conjuntos de números naturais, por isso essas sequências podem ser vistas como conjuntos de números naturais.

A classe de todos as seqüências Martin-Löf aleatórias (binário) é denotada por RAND ou MLR.

História

A primeira definição adequada de uma seqüência aleatória foi dada por Per Martin-Löf em 1966. Pesquisadores anteriores, como Richard von Mises tentou formalizar a noção de um teste para a aleatoriedade, a fim de definir uma seqüência aleatória como aquele que passou todos os testes de aleatoriedade, no entanto, a noção precisa de um teste de aleatoriedade foi deixada vaga. A ideia de Martin-Löf foi usar a teoria da computação para definir formalmente a noção de um teste para a aleatoriedade. Isto contrasta com a ideia de aleatoriedade na probabilidade, em que nenhum elemento particular de um espaço amostral pode considerado aleatório.

A aleatoriedade de Martin-Löf já foi mostrada para admitir muitas caracterizações equivalentes - em termos de compressão, testes de aleatoriedade, e apostas - que tem pouca semelhança com a definição original, mas cada uma delas satisfaz a nossa noção intuitiva de propriedades que seqüências aleatórias devem ter: seqüências aleatórias deve ser incompressíveis, elas devem passar por testes estatísticos de aleatoriedade, e deve ser difícil de ganhar dinheiro apostando neles. A existência de várias definições da aleatoriedade de Martin-Löf e a estabilidade dessas definições em diferentes modelos de computação, evidencia que a aleatoriedade de Martin-Löf é uma propriedade fundamental da matemática e não um acidente de determinado modelo de Martin-Löf. A tese de que a definição da aleatoriedade Martin-Löf captura "corretamente" a noção intuitiva de aleatoriedade é chamada de Tese Martin-Löf- que é um pouco similar a tese de Church-Turing[1].

Três definições equivalentes

A Definição original de Martin-Löf de uma sequência aleatória é baseada foi em termos de conjuntos efetivos nulos , ele definiu uma seqüência ser aleatória, se não for contido em nenhum conjunto efetivo nulo [necessita verificaçao].Leonid Levin e Claus-Peter Schnorr demonstrou uma caracterização em termos de complexidade de Kolmogorov: é uma sequência aleatória, se houver uma limitaçãouniforme de compressibilidade dos seus segmentos iniciais. Schnorr deu uma terceira definição equivalente em termos de martingales (um tipo de estratégia de apostas). O livro de Li e Vitanyi Uma Introdução à Complexidade de Kolmogorov e suas Aplicações tem a introdução para essas idéias.

• Complexidade de Kolmogorov (Schnorr 1973, Levin 1973): Complexidade de Kolmogorov pode ser pensado como um limite inferior sobre a compressibilidade algorítmica de uma sequência finita (de caracteres ou dígitos binários).Ele atribui a cada sequência w a um número natural K(w) que,intuitivamente, mede a duração mínima de um programa de computador (escrito em alguma linguagem de programação fixa), que não tem entrada e dá como saída w quando executado. Dado um número natural c e a sequênciaw, dizemos que w é c- incompressível se $K(w)\geq |w|-c$.

Uma sequência infinita S é Martin-Löf aleatória se e somente se, existe uma constante c tal que todos os prefixos finitos de S são c-incompressíveis.

• Conjuntos efetivos nulos (Martin-Löf 1966): Esta é a definição original de Martin-Löf's. Para uma entrada binária finita w deixamos C_w denotar o cilindro gerado por w. Este é o conjunto de todas as sequências que começam com w infinito, que é um conjunto de base aberta em Cantor espaço. O produto μ(C_w) do cilindro gerado por w é definido por 2^-|w|. Cada subconjunto Cantor espaço é a união de uma seqüência contável de conjuntos abertos disjuntos básicos, ea medida de um conjunto aberto é a soma das medidas de tal seqüência. Um conjunto aberto eficaz é um conjunto aberto que é a união da seqüência de conjuntos abertos básicos determinados por uma sequência recursivamente enumerável strings binárias. O conjuto efetivo nulo or medida efetivo 0 conjunto é uma sequência recursivamente enumerável $U_{i}$ de conjuntos aberto afetivos $U_{i+1}\subseteq U_{i}$ e $\mu (U_{i})\leq 2^{-i}$ para cada número natural i. Cada conjunto efetivo nulo determina a $G_{\delta }$ set of measure 0, ou seja,a intersecção dos conjuntos $U_{i}$.

A sequência é definida como Martin-Löf aleatória se ele não está contido em qualquer lugar >G_\delta</math>, determinado por um conjunto efetivos nulos.