Conteúdo verificado

Teorema do macaco infinito

Assuntos Relacionados: Matemática

Informações de fundo

Arranjar uma seleção Wikipedia para as escolas no mundo em desenvolvimento sem internet foi uma iniciativa da SOS Children. SOS Children trabalha em 45 países africanos; você pode ajudar uma criança em ?frica ?

Com tempo suficiente, um hipotético chimpanzé digitando aleatoriamente seria, como parte da sua produção, quase certamente produzir uma das peças de Shakespeare (ou qualquer outro texto).

O teorema do macaco infinito afirma que um macaco bater as chaves no aleatório em um teclado de máquina de escrever para um tempo infinito quase certamente escreva um texto escolhido em particular, como as obras completas de William Shakespeare . Neste contexto, " quase certamente "é um termo matemático com um significado preciso, eo" macaco "não é um macaco real, mas sim, é uma metáfora para um dispositivo abstrato que produz um seqüência aleatória de letras ad infinitum. O teorema ilustra os perigos do raciocínio sobre o infinito imaginando um vasto mas finito número, e vice-versa. A probabilidade de um macaco digitando uma determinada cadeia de texto, desde que, digamos, Hamlet, é tão pequena que, se a experiência realizada, a chance de um caso ocorrido durante um período de tempo da ordem da idade do universo é minúsculo, mas não zero.

Variantes do teorema incluem múltiplas e até mesmo infinitamente muitos datilógrafos, eo texto-alvo varia entre uma biblioteca inteira e uma única frase. A história dessas declarações pode ser rastreada até Aristóteles Metafísica 's e De natura deorum de Cícero, através de Blaise Pascal e Jonathan Swift, e, finalmente, às declarações modernos com suas máquinas de escrever icônicos. No início do século 20, Émile Borel e Arthur Eddington usaram o teorema para ilustrar os prazos implícitos nos fundamentos da mecânica estatística . Vário Apologistas cristãos, por um lado, e Richard Dawkins, por outro, têm argumentado sobre a adequação dos macacos como uma metáfora para a evolução .

Hoje, o interesse popular nos macacos de digitação é sustentada por numerosas aparições em literatura, televisão e rádio, música, e da Internet. Em 2003, um humor experimento foi realizado com seis Celebes Crested Macacos, mas sua contribuição literária era de cinco páginas que consistem em grande parte da letra S.

Solução

Prova direta

Não é uma prova direta deste teorema. Se dois eventos são estatisticamente independentes, (isto é, não afecta o resultado do outro), então a probabilidade de ambos acontecimento é igual ao produto das probabilidades de cada um de forma independente a acontecer. Por exemplo, se a chance de chuva em Sydney em um determinado dia é de 0,3 ea chance de um terremoto em San Francisco naquele dia é de 0,008, então a chance de ambos acontecendo no mesmo dia é de 0,3 × 0,008 = 0,0024.

Suponha que a máquina de escrever tem 50 teclas, e que a palavra seja digitado é " banana ". Typing ao acaso, a possibilidade de que a primeira letra é digitado b é 1/50, e a possibilidade de que a segunda letra é digitado é também um 1/50, e assim por diante, porque os acontecimentos são independentes. Assim, a possibilidade de a banana primeiros seis letras correspondentes é

(1/50) x (1/50) x (1/50) x (1/50) x (1/50) x (1/50) = (1/50) 6.

Pela mesma razão, a possibilidade de que os próximos seis letras correspondem banana é também (1/50) 6, e assim por diante.

Do acima exposto, a chance de não digitação de banana em um determinado bloco de 6 letras é 1 - (1/50) 6. Como cada bloco é escrito de forma independente, a possibilidade de X n não digitação de banana em qualquer um dos primeiros n blocos de seis letras é

X_n = \ left (1- \ frac {1} {50 ^ 6} \ right) ^ n.

Como n cresce, X n fica menor. Para um N de um milhão, X é N 99,99%, mas para um n de 10 mil milhões de X n é de 53% e para um dos 100 mil milhões de N é 0,17%. Como n se aproxima do infinito, a probabilidade X n se aproxima de zero; isto é, fazendo n suficientemente grande, X n pode ser feito tão pequeno quanto se queira.

O mesmo argumento mostra por que pelo menos um de um número infinito de macacos (quase certamente) produzir um texto tão rapidamente como seria produzida por um datilógrafo humano perfeitamente precisa copiá-lo a partir do original. Neste caso X n = (1 - (1/50) 6) n em que X n representa a probabilidade de que nenhum dos primeiros tipos de banana macacos n correctamente na sua primeira tentativa. Quando consideramos 100 bilhões de macacos, a probabilidade cai para 0,17%, e como o número de macacos n aumenta ao infinito o valor de X n - a probabilidade de os macacos falhando para reproduzir o texto fornecido - diminui para zero. Isso equivale a afirmar que a probabilidade de que um ou mais de um número infinito de macacos produzirá um texto dado na primeira tentativa é de 100%, ou que é quase certo que eles vão fazê-lo.

Cordas infinitas

As duas afirmações acima podem ser declarados em termos mais gerais e de forma compacta em termos de cordas, que são sequências de caracteres escolhidos de algum alfabeto finito:

  • Dada uma seqüência infinita, onde cada personagem é escolhido uniformemente ao acaso, qualquer seqüência finita quase certamente ocorre como uma substring em alguma posição (e, na verdade, um número infinito de posições).
  • Dada uma sequência infinita de cordas infinitas, onde cada personagem de cada cadeia é escolhido uniformemente ao acaso, qualquer seqüência finita quase certamente ocorre como um prefixo de uma dessas cordas (e, na verdade, como um prefixo de infinitamente muitas dessas cadeias no seqüência).

Ambos seguem facilmente a partir do segundo Borel-Cantelli lema. Para o segundo teorema, vamos E k ser o caso em que o k th seqüência começa com o texto dado. Porque isso tem alguma fixa diferente de zero probabilidade de ocorrência p, o E k são independentes, ea soma abaixo diverge,

\ Sum_ {i = 1} ^ \ infty P (E_k) = \ sum_ {i = 1} ^ \ infty p = \ infty,

a probabilidade de que infinitamente muitos dos e k é 1. O ocorrer primeiro teorema é mostrado de forma semelhante; pode-se dividir a seqüência aleatória em blocos que não se sobrepõem correspondentes ao tamanho do texto desejado, e fazer k E o evento onde o k th bloco equivale a seqüência desejada.

Probabilidades

Ignorando pontuação, espaçamento, e capitalização, um macaco de digitação letras uniformemente ao acaso tem uma chance de uma em 26 de digitar corretamente a primeira letra Hamlet. Ele tem uma chance de uma em 676 (26 × 26) de digitar as primeiras duas letras. Uma vez que a probabilidade diminui exponencialmente , em 20 cartas já tem apenas uma possibilidade de uma em 26 20 = 19,928,148,895,209,409,152,340,197,376, aproximadamente equivalente à probabilidade de adquirir 4 bilhetes de loteria consecutivamente e ganhar o jackpot de cada vez. No caso de o texto inteiro de Hamlet, as probabilidades são tão escassamente pequeno que mal pode ser concebido em termos humanos. Diga o texto de Hamlet contém 130.000 cartas (na verdade é mais, mesmo despojado de pontuação), então há uma probabilidade de um em 3,4 × 10 183946 para obter o direito de texto no primeiro julgamento. O número médio de cartas que precisa ser digitado até que o texto aparece também é 3,4 × 10 183946.

Para fins de comparação, existem apenas cerca de 3 × 10 79 átomos de hidrogênio no universo observável e apenas 4,3 × 10 17 segundos transcorridos desde o Big Bang . Mesmo que o universo observável foram preenchidos com macacos digitação de todos os tempos, a sua probabilidade total para produzir uma única instância de Hamlet ainda seria menos do que um em cada 10 183.800. Como Kittel e Kroemer colocou, "A probabilidade de Hamlet é, portanto, de zero em qualquer sentido operacional de um evento ...", ea afirmação de que os macacos devem suceder "dá uma conclusão enganosa sobre muito, muito grandes números." Isto é de seu livro sobre termodinâmica , o campo cujos fundamentos estatística motivou as exposições primeiro conhecidas de macacos de digitação.

História

Mecânica estatística

Em uma das formas em que Probabilists agora sabem este teorema, com a sua "dactiloscópica" [ou seja,] datilografia macacos ( Francês : singes dactylographes; a palavra Francês singe abrange tanto os macacos e os macacos ), apareceu em 1913 O artigo de Émile Borel "Mécanique Statistique et Irréversibilité" ( mecânica estatística e irreversibilidade), e em seu livro "Le Hasard" em 1914. Seus "macacos" macacos não são reais; em vez disso, eles são uma metáfora para uma forma imaginária para produzir uma grande, seqüência aleatória de letras. Borel disse que se um milhão de macacos digitado dez horas por dia, que era extremamente improvável que sua produção seria exatamente igual todos os livros das bibliotecas mais ricas do mundo; e ainda, em comparação, era ainda mais improvável que as leis da mecânica estatística jamais ser violada, mesmo que brevemente.

O físico Arthur Eddington desenhou a imagem do Borel a mais na The Nature of the World Física (1928), escrevendo:

Se eu deixar meus dedos vaguear preguiçosamente sobre as teclas de uma máquina de escrever, pode acontecer que a minha mesa fez uma frase inteligível. Se um exército de macacos foram dedilhando em máquinas de escrever eles poderiam escrever todos os livros do Museu Britânico. A possibilidade de fazer a sua assim é decididamente mais favorável do que a probabilidade de as moléculas que retornam para uma metade do recipiente.

Estas imagens convidam o leitor a considerar a incrível improbabilidade de uma grande, mas finito número de macacos que trabalham para uma grande, mas finito quantidade de tempo produzindo uma obra significativa, e comparar isso com a ainda maior improbabilidade de certos eventos físicos. Qualquer processo físico que é ainda menos provável do que o sucesso de tais macacos é efetivamente impossível, e isso pode se dizer com segurança que tal processo nunca vai acontecer.

Origens e "A Biblioteca Total"

Em um ensaio 1939 intitulado "A Biblioteca Total", o escritor argentino Jorge Luis Borges traçou o conceito infinito-macaco de volta para Aristóteles Metafísica 's. Explicar os pontos de vista Leucipo, que sustentava que o mundo surgiu por meio da combinação aleatória de átomos , Aristóteles observa que os próprios átomos são homogêneos e seus possíveis acordos só diferem na posição e ordenação. O filósofo grego compara isso à maneira que uma tragédia e uma comédia constituída pelas mesmas "átomos", ou seja, caracteres alfabéticos. Três séculos mais tarde, De Cícero natura deorum (Sobre a Natureza dos Deuses) argumentou contra a visão de mundo atomista:

Ele acredita que este pode muito bem acreditar que, se uma grande quantidade de um-e-vinte letras, compostas por ouro ou qualquer outro assunto, foram jogados no chão, eles iriam cair em tal ordem que de forma legível para formar os Anais de Ênio. Duvido fortuna poderia fazer um único verso deles.

Borges segue a história deste argumento através de Blaise Pascal e Jonathan Swift, em seguida, observa que, em seu próprio tempo, o vocabulário mudou. Em 1939, o idioma era "que uma meia dúzia de macacos fornecidas com máquinas de escrever que, em poucos eternidades, produzir todos os livros do Museu Britânico." (Para que Borges acrescenta: "Estritamente falando, um macaco imortal seria suficiente.") Borges imagina então o conteúdo da Biblioteca total que esta empresa iria produzir se realizado em sua plenitude extrema:

Tudo estaria em seus volumes de cegos. Tudo: a história detalhada do futuro, de Ésquilo Os egípcios, o número exato de vezes que as águas do Ganges têm refletido o voo de um falcão, a natureza secreta e verdadeira de Roma, a enciclopédia Novalis teria construído, meus sonhos e meia-sonhos na madrugada de 14 de agosto de 1934, a prova do teorema de Fermat Pierre, os capítulos não escritas de Edwin Drood, esses mesmos capítulos traduzidos para a língua falada pelos garamantes, os paradoxos Berkeley inventou a respeito Tempo, mas não publicar, livros de Urizen de ferro, as epifanias prematuras de Stephen Dedalus, o que seria sem sentido antes de um ciclo de mil anos, o Evangelho gnóstico de Basilides, o canto das sereias cantavam, o catálogo completo da Biblioteca, a prova da inexactidão de que catálogo. Tudo: mas para cada linha sensível ou fato precisa haveria milhões de cacofonias sem sentido, farragoes verbais, e falatórios. Tudo: mas todas as gerações da humanidade poderia passar antes das vertiginosas prateleiras-prateleiras que obliterar o dia e em que o caos mentiras de sempre recompensá-los com uma página tolerável.

Conceito total de biblioteca de Borges foi o tema principal de seu muito lido 1941 história curta " A Biblioteca de Babel ", que descreve um inimaginavelmente vasta biblioteca consistindo de bloqueio câmaras hexagonais, em conjunto contendo todos os volumes possível que poderia ser composto a partir das letras do alfabeto e alguns caracteres de pontuação.

Aplicações e críticas

Evolução

Thomas Huxley é por vezes atribuída erroneamente de propor uma variante da teoria em seus debates com Samuel Wilberforce.

Em seu livro 1931 The Mysterious Universe, rival de Eddington James Jeans atribuído a parábola macaco para um "Huxley", presumivelmente significando Thomas Henry Huxley. Esta atribuição está incorreto. Hoje em dia, algumas vezes é ainda referido que Huxley aplicado o exemplo numa debate agora lendário sobre Charles Darwin 's Origem das Espécies com o bispo anglicano de Oxford, Samuel Wilberforce, realizada em uma reunião do Associação Britânica para o Avanço da Ciência, em Oxford, em 30 de junho de 1860. Esta história não só sofre de uma falta de provas, mas o fato de que em 1860 a própria máquina de escrever ainda tinha que surgir. Primatas ainda eram um tema sensível por outras razões, eo debate Huxley-Wilberforce fez incluem byplay sobre macacos: o bispo perguntou se Huxley era descendente de um macaco no respondeu de sua avó ou o lado de seu avô, e Huxley algo no sentido de que ele seria preferia ser descendente de um macaco do que de alguém que argumentou que desonestamente como o bispo.

Apesar do original mix-up, os argumentos macaco-e-máquina de escrever são agora comuns em argumentos sobre a evolução. Por exemplo, Doug Powell argumenta como um Apologista cristão que mesmo que um macaco acidentalmente tipos as letras de Hamlet, ele não foi capaz de produzir Hamlet porque faltou a intenção de comunicar. Sua implicação paralela é que as leis naturais não poderia produzir o conteúdo de informação em DNA . Um argumento mais comum é representado por John MacArthur, que afirma que as mutações genéticas necessárias para produzir uma tênia de uma ameba são tão improvável quanto um macaco digitando o monólogo de Hamlet, e, portanto, as chances contra a evolução de toda a vida são impossíveis de superar.

Biólogo evolucionário Richard Dawkins emprega o conceito macaco que datilografa em seu livro de 1986 O Relojoeiro Cego para demonstrar as habilidades de seleção natural na produção biológica complexidade do aleatório mutações. No experimento de simulação que ele descreve, Dawkins tem a sua Programa Weasel produzir a frase Hamlet Parece-me que é como um WEASEL digitando frases aleatórias, mas constantemente congelar as partes da saída que já corresponder ao objetivo. O ponto é que a geração de seqüência aleatória serve apenas para fornecer matérias-primas, enquanto a selecção transmite a informação.

Um caminho diferente para rejeitar a analogia entre evolução e um macaco sem restrições reside no problema que os tipos de macaco apenas uma letra de cada vez, independentemente das outras letras. Hugh Petrie argumenta que uma configuração mais sofisticada é necessária, no seu caso, não para a evolução biológica, mas a evolução das idéias:

A fim de obter a analogia correta, teríamos de equipar o macaco com uma máquina de escrever mais complexa. Ele teria de incluir frases inteiras Isabelino e pensamentos. Ele teria de incluir crenças Isabelino sobre os padrões humanos de ação e as causas, moralidade Isabelino e de ciência e padrões linguísticos para expressar estes. Seria, provavelmente, ainda tem que incluir um relato dos tipos de experiências que moldaram a estrutura da crença de Shakespeare como um exemplo particular de um elizabetano. Então, talvez, possamos permitir que o macaco para jogar com uma máquina de escrever e produzir tais variantes, mas a impossibilidade de obtenção de uma peça de Shakespeare não é mais óbvio. O que é variado realmente encapsular uma grande quantidade de conhecimento já alcançados-.

James W. Valentine, embora admitindo que a tarefa do macaco clássico é impossível, acha que há uma analogia interessante entre Inglês escrito eo metazoan genoma neste outro sentido: ambos têm "combinatórios, estruturas hierárquicas" que limitam muito o imenso número de combinações ao nível do alfabeto.

A teoria literária

RG Collingwood argumentou em 1938 que a arte não pode ser produzido por acidente, e escreveu como um sarcástico de lado para seus críticos,

... Alguns ... negaram essa proposição, apontando que, se um macaco jogado com uma máquina de escrever ... ele iria produzir ... o texto completo de Shakespeare. Qualquer leitor que não há nada a fazer pode se divertir calculando quanto tempo levaria para que a probabilidade de ser vale a pena apostar tem. Mas o interesse da sugestão está na revelação do estado mental de uma pessoa que pode identificar as "obras" de Shakespeare com a série de letras impressas nas páginas de um livro ...

Nelson Goodman tomou a posição contrária, ilustrando o seu ponto junto com Catherine Elgin pelo exemplo de Borges '" Pierre Menard, autor do Quixote ",

O que Menard escreveu é simplesmente outra inscrição do texto. Qualquer um de nós pode fazer o mesmo, como prensas de impressão lata e fotocopiadoras. Na verdade, somos informados, se um número infinito de macacos ... uma acabaria por produzir uma réplica do texto. Essa réplica, mantemos, seria tanto uma instância da obra, Don Quixote, como Cervantes manuscrito ', manuscrito de Menard, e cada cópia do livro que já tenha sido ou venha a ser impresso.

Em outro escrito, Goodman elabora, "Que o macaco pode ser suposto ter produzido sua cópia faz aleatoriamente nenhuma diferença. É o mesmo texto, e é aberto a todos as mesmas interpretações ...". Gérard Genette rejeita o argumento de Goodman como implorando a pergunta.

Para Jorge JE Garcia, a questão da identidade de textos leva a uma outra questão, que de autor. Se um macaco é capaz de escrever Hamlet, apesar de não ter intenção de significado e, portanto, desqualificando-se como um autor, então parece que os textos não requerem autores. As soluções possíveis incluem dizendo que quem encontra o texto e identifica-lo como Hamlet é o autor; ou que Shakespeare é o autor, o macaco seu agente, e no visor apenas um usuário do texto. Estas soluções têm suas próprias dificuldades, na medida em que o texto parece ter um significado distinto dos outros agentes: e se o macaco opera antes de Shakespeare nasceu, ou se Shakespeare nunca é carregado, ou se ninguém nunca encontra typescript do macaco?

Geração de números aleatórios

O teorema diz respeito a um pensou experiência que não pode ser totalmente realizada na prática, uma vez que é previsível que requerem quantidades proibitivos de tempo e recursos. No entanto, ele tem inspirado os esforços na geração de texto aleatório finito.

Um programa de computador executado por Dan Oliver de Scottsdale, Arizona, de acordo com um artigo em The New Yorker, veio com um resultado em 4 de agosto de 2004: Depois que o grupo havia trabalhado para 42162500000 bilhões de bilhões de anos, um dos "macacos" digitadas ", VALENTIM. Cessar toIdor: eFLP0FRjWK78aXzVOwm) - '; 8.t. . . "Os primeiros 19 cartas de esta sequência pode ser encontrada em" Os Dois Cavalheiros de Verona ". Outras equipes têm reproduzido a partir de 18 caracteres" Timon de Atenas ", 17 de" Troilus e Cressida ", e 16 a partir de" Richard II ".

Um site intitulado The Monkey Shakespeare Simulator, lançado em 1 de Julho, 2003 , continha uma Applet Java que simula uma grande população de macacos digitando aleatoriamente, com a intenção declarada de ver quanto tempo leva os macacos virtuais para produzir uma peça de Shakespeare completo do começo ao fim. Por exemplo, é produzido a partir desta linha parcial Henry IV, Part 2, relatando que ele levou "2.737.850 milhões de bilhões de bilhões de bilhões de anos-macaco" para chegar a 24 caracteres de correspondência:

RUMOR. Abra seus ouvidos; 9r "5j5 &? OWTY Z0d ...

Devido a limitações de potência de processamento, o programa usa um modelo probabilístico (usando um gerador de números aleatórios ou RNG) em vez de realmente gerar texto aleatório e comparando-a com Shakespeare. Quando o simulador "detecta uma coincidência" (isto é, o RNG gera um determinado valor ou um valor dentro de um determinado intervalo), o simulador simula o jogo através da geração de texto correspondente.

Perguntas sobre as estatísticas que descrevem a frequência com que um macaco ideal deve digitar determinadas seqüências podem motivar testes práticos para geradores de números aleatórios bem; Estes vão desde o simples para o "bastante sofisticada". Professores de ciência da computação George Marsaglia e Denunciar Arif Zaman que eles costumavam chamar esses testes "m- sobreposição testes uplos "em conferência, desde que digam respeito à sobreposição de m-tuplas de elementos sucessivos numa sequência aleatória. Mas eles descobriram que chamando-os de" testes de macaco "ajudou a motivar a idéia com os alunos. Eles publicaram um relatório sobre a classe de testes e seu resultados para vários RNGs em 1993.

Macacos reais

Behavioristas primatas Cheney e Seyfarth observação de que macacos reais seria de fato tem que confiar na chance de ter alguma esperança de produzir Romeu e Julieta . Ao contrário de macacos e, particularmente, os chimpanzés , a evidência sugere que os macacos não têm um teoria da mente e são incapazes de diferenciar entre seus próprios e os conhecimentos dos outros, emoções e crenças. Mesmo que um macaco poderia aprender a escrever uma peça e descrever os caracteres 'comportamento, não poderia revelar os personagens' mentes e assim construir uma tragédia irônica.

Em 2003, docentes e alunos do Universidade de Plymouth curso Medialab Artes utilizado um subsídio £ 2.000 do Conselho de Artes para estudar a produção literária de macacos reais. Eles deixaram um teclado de computador no gabinete de seis Celebes Crested Macaques em Paignton Zoo em Devon em Inglaterra por um mês, com um link de rádio para transmitir os resultados em um site. Um pesquisador, Mike Phillips, defendeu a despesas como sendo mais barato do que a realidade TV e ainda "muito estimulante e visualização fascinante".

Não só os macacos produzem nada mais que cinco páginas que consistem em grande parte da carta S, o principal masculino começou por bashing o teclado com uma pedra, e os macacos continuaram urinando e defecando sobre ele. Diretor científico do zoológico observou que a experiência teve "pouco valor científico, exceto para mostrar que a teoria do" macaco infinito "é falho". Phillips disse que o projecto financiado pelo artista era principalmente arte da performance, e que tinham aprendido "muitíssimo" a partir dele. Ele concluiu que os macacos "não são geradores aleatórios. Eles são mais complexas do que isso. ... Eles foram bastante interessados na tela, e eles viram que, quando digitou uma letra, algo aconteceu. Houve um nível de intenção lá."

Cultura popular

O teorema do macaco infinito e seu imaginário associado é considerado um popular, e ilustração proverbial da matemática da probabilidade, amplamente conhecidos do público em geral por causa de sua transmissão através da cultura popular e não por causa de sua transmissão através da sala de aula.

A natureza duradoura, difundida e popular do conhecimento do teorema foi referido na introdução a um artigo de 2001, "Macacos, Máquinas de escrever e Redes - a Internet na Luz da Teoria da Accidental Excellence" (Hoffmann e Hofmann). Em 2002, um Artigo do Washington Post, disse: "Muitas pessoas têm me diverti com a famosa noção de que um número infinito de macacos com um número infinito de máquinas de escrever e uma quantidade infinita de tempo poderia, eventualmente, escrever as obras de Shakespeare." Em 2003, o já mencionado Experimento financiado envolvendo macacos reais e um teclado de computador Arts Council recebeu ampla cobertura da imprensa. Em 2007, o teorema foi listada por A revista Wired em uma lista de oito clássico experiências de pensamento.

A história das imagens de 'macacos digitando' remonta pelo menos tanto quanto o uso do Borel da metáfora em seu ensaio em 1913, e esse imaginário retornou muitas vezes desde então em uma variedade de meios de comunicação. Hoje, o interesse popular nos macacos de digitação é sustentada por numerosas aparições em literatura, televisão e rádio, música, e da Internet, bem como graphic novels e stand-up comedy rotinas.

Retirado de " http://en.wikipedia.org/w/index.php?title=Infinite_monkey_theorem&oldid=203983193 "