sexta-feira, 8 de agosto de 2008

O espelho de Einstein

Houve um tempo em que os físicos se perguntavam qual o meio responsável pelo deslocamento da luz. Sabia-se que a luz conseguia se propagar no vácuo, mas os cientistas da época consideravam isso paradoxal e propuseram que o universo era permeado por uma substância chamada éter. O éter era um tanto quanto estranho. Era considerado incrivelmente forte e no entendo estranhamente insubstancial. Era transparente, sem atrito e quimicamente inerte. Estava em toda parte ao nosso redor e, no entanto, era difícil de identificar já que ninguém jamais o vira, agarrara ou dera de cara com ele. Einstein ainda era um jovem estudante de 16 anos quando propôs uma experiência mental para mostrar que o éter não existia. Ele imaginou o que aconteceria se pudesse viajar no espaço com a velocidade na luz e um espelho a sua frente. Particularmente, ele indagava se seria capaz de ver o próprio reflexo. Pela teoria da época, a luz era supostamente transportada pelo éter e isso implicava que ela se deslocava com a velocidade da luz (300.000 km/s) em relação ao éter. Na experiência mental de Einstein, ele, seu rosto e o espelho se deslocavam também com a velocidade da luz. Assim, a luz deveria deixar o rosto de Einstein e viajar até o espelho, mas nunca conseguiria deixar seu rosto, e muito menos chegar ao espelho, porque tudo se movia com a velocidade da luz. E como a luz não podia alcançar o espelho, então ela não seria refletida de volta e, conseqüentemente, Einstein não conseguiria ver o seu reflexo. Isso era totalmente chocante, pois contrariava o princípio da relatividade de Galileu, que dizia que uma pessoa que se deslocasse numa velocidade constante, não poderia determinar se estava se movendo ou parada. Com a experiência mental de Einstein, alguém que estivesse viajando com a velocidade da luz conseguiria saber do seu movimento, pois o seu reflexo desapareceria. Alguma coisa tinha que estar errada. Ou a relatividade de Galileu estava errada ou a experiência mental de Einstein tinha alguma falha fundamental. Einstein concluiu que a luz não viaja a uma velocidade fixa em relação ao éter, que a luz não é transportada pelo éter e que o éter nem sequer existia. [E isso tudo com 16 anos.] Ele pensou sobre o assunto intermitentemente durante os anos seguintes e chegou à conclusão que a luz se desloca a uma velocidade constante em relação ao observador. Isso implica que não importa quais as circunstâncias ou como a luz está sendo emitida, cada um de nós pessoalmente mede a velocidade da luz. Essa idéia parece absurda e, no entanto, ficou provado que Einstein estava certíssimo. E foi a partir daí que surgiu a teoria da relatividade especial de Einstein e as suas idéias de contração do espaço e dilatação do tempo.

sexta-feira, 29 de fevereiro de 2008

O Livro dos Códigos

Nesses últimos dias eu li um livro chamado O Livro dos Códigos, de Simon Singh. O livro conta a história da criptografia, desde a antiguidade até a criptografia quântica. Mostra como as cifras e a busca pelo sigilo avançaram ao longo do tempo. Na antiguidade, se usava muito a esteganografia, que consiste em esconder a mensagem ao invés de cifrá-la. Uma das primeiras cifras utilizadas que se tem registro é a cifra de César. Ela consiste em você fazer um deslocamento no alfabeto. Por exemplo, se o deslocamento for de 1, PATY seria cifrado como QBUZ. Essa cifra claramente é muita fraca e fácil de quebrar. Esse tipo de cifra é chamada monoalfabética, pelo fato óbvio de usar apenas um alfabeto. Durante muito tempo os criptógrafos (as pessoas que cifram) ganharam a batalha com os criptoanalistas (aqueles que tentam quebrar esses códigos). Foram desenvolvidas cifras monoalfabéticas mais complicadas, mas os árabes inventaram uma técnica para quebrar essas cifras chamada de análise de freqüência. Assim, os criptoanalistas passaram a frente nessa batalha. Os criptógrafos então inventaram uma cifra polialfabética que eles chamavam de “A cifra indecifrável”. Ela foi assim considerada por muito tempo, mas Babbage conseguiu decifrá-la. Durante a segunda guerra mundial, a criptografia exerceu um papel fundamental. Os alemães criaram a maquina de encriptação Enigma, que eles consideravam muito segura. Mas os poloneses e depois os ingleses conseguiram quebrar e decifrar as mensagens do Enigma, afetando muito o curso da guerra. Com o desenvolvimento dos computadores e posteriormente da internet, havia na área uma preocupação enorme com relação à segurança. Como fazer para manter a segurança num ambiente como a internet? Para muitas transações, segurança é fundamental, como transações bancarias e de governo. Foram inventados diversos algoritmos de criptografia muito eficientes, mas que tinham um problema fundamental: a distribuição de chaves. Se Alice deseja se comunicar com Bob, eles precisam combinar uma chave para ser usada no algoritmo de encriptação. Desde a antiguidade, o sigilo era garantido através da chave e não do fato de o oponente conhecer o método usado para cifrar. O inimigo podia conhecer o método, mas contanto que ele não conhecesse a chave, ele não conseguiria decifrar. Esses métodos de cifrar evoluíram bastante ao longo do tempo, mas o problema da distribuição das chaves continuou. Se Alice quer se comunicar com Bob, como eles fazem para combinar a chave usada? Alice poderia mandar a chave pela internet para Bob, mas se o canal não é seguro para se enviar mensagens, tampouco vai ser seguro para enviar a chave. Então Alice e Bob precisariam encontrar outra maneira de trocar a chave. Eles poderiam se encontrar pessoalmente, por exemplo. Porém, isso requer bastante esforço e não é viável para as aplicações comerciais. Imagine uma empresa onde cada par de funcionários precisa ter a sua chave para se comunicar e essa empresa tem 200 funcionários. Casa funcionário deveria saber a chave para se comunicar com os outros 199, tarefa um tanto inviável. E quanto mais cresce o número de funcionários ou pessoas querendo se comunicar, mais complicado fica para fazer essa troca de chaves. Era necessária uma solução urgente para o problema da distribuição de chaves, mas a maioria dos estudiosos da época achava que o problema da distribuição de chaves era insolúvel. Foi aí que surgiram as idéias de dois pesquisadores, Whitfield Diffie e Martin Hellman. Eles criaram o conceito de criptografia de chave pública, que resolvia esse problema da distribuição de chaves. A idéia deles é que cada pessoa tivesse a sua chave privada e sua chave pública. A chave pública é usada para cifrar as mensagens e é de conhecimento público, todo mundo pode ter acesso. Já a chave privada fica em poder do seu dono que a guarda em segredo, sendo usada para decifrar as mensagens cifradas com a respectiva chave pública. Assim, se Alice deseja mandar uma mensagem para Bob, ela cifra a mensagem com a chave pública de Bob e envia a mensagem cifrada para ele. Só quem vai poder decifrá-la é Bob, pois apenas ele sabe a sua chave privada que é necessária para fazer isso. Assim, eles não precisam mais trocar chaves porque o único conhecimento que Alice precisa para mandar uma mensagem para Bob é a sua chave pública, a qual todos têm acesso e não dá meios de se encontrar a chave privada. Diffie e Hellman tiveram essa maravilhosa idéia, mas não conseguiram conceber um sistema que funcionasse eficientemente dessa maneira na prática. A partir do lançamento das idéias deles, começou-se uma busca por uma implementação viável da criptografia de chave pública. Ela veio um tempo depois com três pesquisadores chamados Ron Rivest, Adi Shamir, Len Adleman. Eles inventaram o algoritmo RSA, que é considerada por muitos a melhor implementação da criptografia de chave pública. Esse algoritmo é usado largamente na internet, para manter a segurança de transações bancarias, e-commerce e muitas outras aplicações. No RSA, a chave privada é basicamente dois números primos de um tamanho enorme e a chave pública é a multiplicação desses dois primos. O dono da chave privada consegue facilmente gerar a chave pública, porque a multiplicação é uma tarefa fácil. Já a fatoração de um número nos seus dois fatores primos é um tanto complicado quando o tamanho da entrada cresce. Atualmente, usa-se um tamanho de chave da ordem em torno de 10 elevado a 308, o que levaria todos os computadores do mundo mais do que a idade do universo para conseguir achar a resposta. Por isso, o RSA é considerado um algoritmo seguro. Com o advento dos computadores quânticos, essa segurança poderia ser quebrada, e aí teria que se inventar [e até já foi inventado] outro tipo de método criptográfico para conseguir manter o sigilo. Ah sim, e eu recomendo o livro, muito interessante.

domingo, 10 de fevereiro de 2008

20.000 Léguas Matemáticas

Essa semana eu li o livro 20.000 léguas matemáticas, de A. K. Dewdmey. Ele fala sobre a busca do professor Dewdney pela resposta de duas grandes perguntas: “Por que a matemática é tão incrivelmente útil nas ciências naturais?” e “A matemática é descoberta ou criada?”. Para isso, ele se encontrou com quatro estudiosos para tentar responder a essas perguntas. O primeiro deles foi Petros Pygonopolis, um historiador da matemática e da ciência, na antiga cidade grega de Mileto. O segundo foi o astrônomo árabe Jusuf al-Flayli no Egito. O terceiro encontro foi com Maria Canzoni, uma física de Veneza. Por último, ele se encontrou com Sir John Brainard, um matemático de Oxford. Os quatro possuíam opiniões um tanto quanto diferentes, mas todos concordavam com o mesmo ponto: a matemática é sim descoberta. Mesmo depois de ler todo esse livro com diversas opiniões diferentes acerca do assunto, eu continuo com a minha opinião que eu dei nessa postagem: A matemática é descoberta. Ela já existe, nós apenas vamos descobrindo as relações e inventando abstrações para representá-la. Existe a hipótese pitagórica, que diz que: ”O cosmo e tudo que há nele são regidos por leis matemáticas.” Pitágoras ainda ia além e dizia que o universo poderia ser todo descrito por inteiros. Nesse ponto eu não concordo. Houve uma parte do livro que me chamou uma particular atenção. Um matemático inglês chamado David Gridbourne julgava ter produzido criaturas vivas em seu computador. Ele desenvolveu um autômato celular chamado 2DWORLD, que é basicamente um universo bidimensional com a forma de uma vasta esfera. Esse autômato é regido por regras simples que imitam as equações da física moderna. Ele começou aleatoriamente distribuindo 0 ou 1 a cada célula dessa unidade. Isso acabou, para surpresa do próprio Gridbourne, gerando um cosmo bidimensional com estruturas complexas. Ele disse o seguinte a respeito desse universo: “E está [vivo]. Algumas regras da física parecem garantir o surgimento de níveis organizacionais, um após o outro, aparentemente de maneira infindável. Nesse nível, o sistema chegou a estruturas que se propagam interminavelmente. E elas têm mudado, desde que surgiram pela primeira vez. Decididamente, estão ficando mais complexas, e têm uma espécie de código genético, embora ele se baseie em estruturas muito diferentes da do nosso. ” Ele ainda considera que é possível que essas estruturas possam desenvolver a ciência e acabar descobrindo as leis que ele instalou no seu espaço celular e acha até possível que elas descubram que só existem em um computador, mas não teriam a menor idéia em qual computador nem onde. Uma viagem isso né? Enfim, o livro é bom. Recomendo a leitura por quem se interesse pelas perguntas de Dewdney e pela história da matemática.

quinta-feira, 10 de janeiro de 2008

Infinito - Parte 1 [de ∞]

Infinito… Qual a primeira coisa que nos vem à cabeça quando pensamos em infinito? Talvez um número indefinidamente grande, a quantidade de números naturais ou reais ou complexos ou o que quer que seja. Mas nada disso nos parece muito familiar, não parece muito próximo a nossa realidade cotidiana. Eu poderia te dizer: imagine o número de grãos de areia de todas as praias de todo o planeta. É um número bastante grande, mas não é nada comparado ao infinito. Imagine agora o número de átomos da nossa galáxia. É um numero absurdamente maior e inimaginável, mas mesmo assim não é infinito. Quando se pensa sobre o infinito, nos deparamos com vários paradoxos. Se eu acrescentar um elemento ao infinito, quanto eu tenho? Infinito. Se eu tirar um elemento do infinito, quanto eu tenho? Infinito. Eu posso acrescentar ou tirar milhares, milhões, bilhões e continuará sendo infinito. Muitos matemáticos durante toda a história da humanidade tentaram estudar sobre o infinito e acabaram desistindo, parecia uma coisa que não tinha muita explicação. Galileu afirmou que o infinito é um conceito divino e, por isso, só Deus é capaz de entender. Foi só no final do século XIX que houve avanços no estudo do infinito, com George Cantor. Quando eu pergunto a alguém a sua opinião sobre a relação entre o conjunto dos números naturais {0, 1, 2, 3, 4, ...} e o conjunto dos números inteiros {..., -4, -3, -2, -1, 0, 1, 2, 3, 4, ...}, quem é maior ou se eles são do mesmo tamanho, normalmente recebo a resposta: é claro que o conjunto dos inteiros é maior do que o conjunto dos naturais. A intuição nos leva a crer que existem mais inteiros do que os naturais, aparentemente até o dobro, mas ela está errada: o tamanho do conjunto dos números naturais e inteiros tem o mesmo tamanho. Isso até choca um pouco no início, mas com uma simples prova matemática pode-se mostrar que isso é verdade. Eu posso afirmar que dois conjuntos têm o mesmo tamanho se eu conseguir associar cada elemento de um dos conjuntos com um elemento do outro conjunto, certo? Por exemplo, se eu tiver um conjunto A = {1, 2, 3} e B = {a, b, c}, eu posso fazer a correspondência a –> 1, b –> 2 e c –> 3 e com isso mostrar que os dois conjuntos têm o mesmo tamanho. Isso se chama correspondência biunívoca. Se eu conseguir fazer uma correspondência biunívoca entre os elementos de dois conjuntos quaisquer, eu posso afirmar que esses dois conjuntos têm o mesmo tamanho. Essa é a maneira usada para comparar conjuntos infinitos, já que com conjuntos infinitos nós não temos a opção de contar o número de elementos de um conjunto e do outro para ver se são iguais. Agora vamos fazer uma correspondência biunívoca entre os números naturais e os números inteiros. Vamos listar os números naturais da seguinte maneira: 0, 1, 2, 3, 4, 5, 6, ... e vamos listar os números inteiros da seguinte maneira: 0, -1, 1, -2, 2, -3, 3, -4, 4, .... Assim iremos fazer a seguinte correspondência: 0 –> 0, 1 –> 1, 2 –> -1, 3 –> 2, 4 –> -2, 5 –> 3, 6 –> -3, e assim por diante. Podemos continuar fazendo essa correspondência indefinidamente, pois a quantidade de números é infinita. Por mais que avancemos, nunca conseguiremos chegar a algum limite que faça os inteiros superar os naturais. São infinitos e têm exatamente o mesmo tamanho. Com um raciocínio análogo, podemos mostrar que os naturais, naturais pares, inteiros, inteiros negativos, racionais e vários outros conjuntos têm exatamente o mesmo tamanho. E aí podemos pensar: todo infinito é igual, qualquer conjunto infinito tem o mesmo tamanho do que qualquer outro conjunto infinito. Verdade? Não. O conjunto dos números reais tem um tamanho infinito que é maior do que o conjunto dos números naturais. Ainda mais chocante: o tamanho do conjunto dos números reais entre 0 e 1 é maior do que o conjunto de todos os inteiros. Mas o que leva dois conjuntos infinitos a não terem o mesmo tamanho? Qual a diferença na natureza deles que faz eles serem tão diferentes? A diferença é a noção de contagem. Se eu pego o conjunto dos números naturais, eu consigo ir contando os elementos. Obviamente eu nunca iria parar de contar, mas o que importa aqui é que eu consigo contar. E se eu escolher dois naturais, quaisquer, eu consigo dizer com exatidão o número [finito] de naturais que existem entre eles. Por exemplo, se eu pegar 2 e 1.989.123, eu posso afirmar que o número de naturais entre esses dois números é 1.989.120. Agora pegue dois reais quaisquer, por exemplo, 0 e 1. Tente listar todos os reais entre esses dois números. Você nunca conseguirá listar todos os elementos. Essa é a diferença na natureza desses dois conjuntos infinitos que faz eles terem tamanhos diferentes. Agora sabe o que Cantor provou que é ainda mais desconcertante? Ele provou que não só existem dois tamanhos diferentes do infinito, como existem infinitos tamanhos diferentes para o infinito. Ou seja, dado qualquer conjunto infinito, conseguimos montar um conjunto que tem um tamanho infinito maior do que ele. E isso nunca tem fim. Isso é uma afirmação um tanto quanto audaciosa e demorou algum tempo até que os matemáticos aceitassem que Cantor estava certo. Tem muitas outras questões interessantes a respeito do infinito, mas fica para uma próxima postagem.