Blogs

23.junho.2010 09:03:39

Alan Turing, 98

Cá estava eu achando que não ia ter o que blogar hoje, e eis que encontro um tuíte da @CyberDecker (que mantém o blog CyberGi) lembrando que hoje é — ou seria — aniversário do matemático britânico Alan Turing. Se não tivesse sido levado ao suicídio pela política cruel de repressão ao homossexualismo que vigorava no Reino Unido na década de 50, ele poderia estar fazendo 98 anos.

Tratar de Turing num blog é quase desrespeitoso. Ele teve uma vida (e realizou uma obra) que requer volumes inteiros para ser bem apresentada; seu vulto simplesmente não cabe numa postagem de 500 palavras. Suas contribuições à ciência — a “Máquina de Turing”, o “Teste de Turing”, entre outras — têm uma enorme riqueza não só em termos de potencial tecnológico, mas também conceitual e filosófico.

Quer saber mais? A Wikipedia está aí para isso.

Mas vou mencionar aqui uma descoberta de Turing que recebe relativamente pouca atenção dos popularizadores, mas que me parece ter implicações monumentais. Estou me referindo ao “Halting Theorem”, ou Teorema da Parada.

Pense no WordPress, o programa que estou usando para blogar, e no texto desta postagem, o “input” que estou dando ao programa.

Assim que eu clicar em “publicar”, o programa vai começar a processar o input, e uma de duas coisas pode acontecer: o processamento terminar em algum momento — com a provável publicação do texto no blog ou, falhando isso, a emissão de algum tipo de mensagem de erro — ou o WordPress travar e ficar mastigando meu input ad infinitum, sem apresentar nenhum resultado.

(Estou abstraindo outras possíveis complicações, como minha conexão com a internet cair, o Windows dar pau, o iTunes que também estou rodando travar tudo… Este é apenas um exemplo idealizado)

Seria interessante se houvesse um outro programa (dá para imaginar um site com essa função) onde, se você informasse que programa está usando — WordPress, MS Word, Excel, etc. — e o input que pretende fornecer, gerasse já de cara uma previsão de resultado: “vai rodar” ou “vai travar”. Pouparia muito trabalho!

Seria interessante, mas é impossível. Alan Turing provou isso, em 1936. Não é possível criar um programa genérico capaz de, dado um outro programa qualquer X e um input para X, prever se a computação vai dar certo.

Soa meio inócuo, não? Mas pense: isso significa que um programa de computador – um conjunto de instruções lógicas, perfeitamente determinístico, movido a zero e um, sim ou não — pode ser essencialmente imprevisível.

Além de representar um álibi para programadores, que podem alegar que alguns bugs são inevitáveis porque imprevisíveis, esse resultado poderia também informar a discussão filosófica sobre determinismo e livre arbítrio.

O argumento completo está, se não me engano, em Freedom Evolves, de Daniel C. Dennett, mas resumindo: se as coisas mais determinísticas que somos capazes de criar — programas de computador — conseguem, a partir de um certo grau de complexidade, ser imprevisíveis, por que nossas mentes, que são muito mais complexas (e muito mais imprevisíveis) que os programas que criamos não poderiam ser simplesmente fruto do determinismo das leis naturais?

Enfim: morto há mais de 50 anos, Turing continua a alimentar discussões fundamentais.

comentários (19) | comente

Tweet
A + A -

19 Comentários Comente também

23/06/2010 - 09:43
Enviado por: Alberto Fabiano

@Carlos,

Da sua teoria da computabilidade a sua contribuição na para inteligência artificial e redes neurais a obra de Turing é brilhante e seminal.

Entendo que ele tende a alimentar discussões ad infinitum.

[]s++;

responder este comentário denunciar abuso
23/06/2010 - 10:14
Enviado por: Osmar Neves

No Calvinismo, nossas mentes são ações do determinismo divino uma vez que Deus é soberano. Nós fazemos escolhas mas essas escolhas jamais podem ser alheias ou livres da ação causal divina. Nossas mentes são imprevisíveis para nós, seres finitos, mas não para Deus, ser onisciente, e primeiro motor da realidade. No Calvinismo, Deus conhece tudo o que decreta e como ele decreta tudo, ele conhece todas as coisas.

responder este comentário denunciar abuso
23/06/2010 - 10:24
Enviado por: Kohlmeyer

Boa lembrança! Acho a história do Turing trágica, um herói matemático levado ao suicídio. Merece ser sempre lembrada.

responder este comentário denunciar abuso
23/06/2010 - 12:04
Enviado por: Jaime Collier Coeli

“Fruto do determinismo das leis naturais”? Mas se os maiores determinismos (observe o plural) revelam ser imprevisiveis, conclue-se que os deteminismos (no plural) são aleatorios. Determinismo (de qualquer marca) é coisa de zemané.

responder este comentário denunciar abuso
- 23/06/2010 - 15:03
  Enviado por: Osmar Neves
  
  Você notou a incoerência da citação do artigo mas tirou daí uma conclusão equivocada. Nós não sabemos se há determinismo ou se a realidade é aleatória, a menos que Alguém que saiba a resposta nos revele. E é isso que o Calvinismo diz: Deus é soberano, conhece tudo o que decreta e como ele decreta tudo, ele conhece todas as coisas.
  responder este comentário denunciar abuso
- 23/06/2010 - 15:10
  Enviado por: Carlos Orsi
  
  Não necessariamente… Por exemplo, se você aceita a afirmação de que o estado do Universo num dado instante “t” é causado, única e exclusivamente, pelo estado do Universo no instante “t-1″, então você tem de aceitar que o Universo em “t” é determinado pelo Universo em “t-1″ — o que é um tipo de determinismo.
  responder este comentário denunciar abuso
23/06/2010 - 13:58
Enviado por: Eduardo

Caro Carlos,

O Teorema da Parada é um desdobramento do Teorema de Incompletude de Gödel. De uma olhada no livro MetaMath do Chaitin. Acho que você vai achar alguns temas interessantes apra sua coluna.

responder este comentário denunciar abuso
23/06/2010 - 15:12
Enviado por: FRANCISCO CARLOS COUTO DE MORAES

EXCELENTE lembrança. Também é notável a decifração do código secreto dos nazistas, na operação “Enigma”, que há quem diga que abreviou em alguns anos a II Guerra. Com todo o respeito que tenho pelo Deus do Calvinismo, tanto que escrevo Seu Nome, Seus Pronomes e mais alguns Correlatos com Maiúsculas, a idéia de que Ele criou muito mais pecadores do que santos – e dizem que sabia o que estava fazendo – corrobora meu axioma do Groucho-Marxismo, do qual sou o primeiro e maior proleta, por assim dizer: Não acredito na perfeição do Deus que me criou. A sociedade inglesa é muito hipócrita, porque é governada pela MAIS ANTIGA E ACEITA CORPORAÇÃO DO CRIME ORGANIZADO – A WOLF GANG.

responder este comentário denunciar abuso
- 23/06/2010 - 19:06
  Enviado por: Haemerken
  
  Vida longa ao Grouxo-Marxismo. O novo determinismo pode assumir a Suprema Autoridade do mundo, não fazer prisioneiros e começar a cobrar dizimos. Decretará um novo t-0 e, a partir de t-1, já terá convencido os sobreviventes de sua Verdade.
  responder este comentário denunciar abuso
23/06/2010 - 19:41
Enviado por: Mauricio Leandro

Meritos de Turing a parte, e aproveitando a carona na conversa sobre determinismo, esse “levado ao suicídio pela política cruel de repressão ao homossexualismo” nao pegou bem. A necessidade nao leva alguem a prostituiçao, tampouco a pobreza leva ninguem ao crime…

responder este comentário denunciar abuso
- 23/06/2010 - 21:42
  Enviado por: Carlos Orsi
  
  Digamos que se seu governo forçar você a tomar hormônios e a se afastar das pessoas que ama para não jogá-lo nas galés, pode-se dizer que se está sendo “levado” a alguma proposição trágica…
  responder este comentário denunciar abuso
- 24/06/2010 - 20:01
  Enviado por: Mauricio Leandro
  
  Continuo em desacordo. Se fosse assim, Mandela nunca teria saido da prisao vivo. Afinal o governo tambem fez e desfez dele. O mesmo poderia ser dito de milhoes de judeus que sairam vivos dos campos de concentraçao nazistas. Acho que o mais correto seria dizer que, depois de tanto sofrimento, Turing se suicidou. Afinal, a decisao final foi dele.
  responder este comentário denunciar abuso
24/06/2010 - 07:04
Enviado por: hacs

Oi,

Posso sugerir um tema? Seria interessante uma materia sobre os problemas IP (Merlin e Artur).

Abs

responder este comentário denunciar abuso
- 24/06/2010 - 07:51
  Enviado por: Carlos Orsi
  
  Sugestão anotada!
  responder este comentário denunciar abuso
24/06/2010 - 09:57
Enviado por: Thiago Serra

Prezado Carlos,

Achei muito interessante e ousado o seu artigo sobre Turing. Fugiu ao lugar comum de se falar apenas sobre o Teste de Turing e ainda ousou divagar sobre o Teorema da Parada sem dar nenhum furo. Eu não sou jornalista mas já fui blogueiro quando estava no intercâmbio e sempre era pego tirando conclusões indevidas, hehehe.

A Teoria da Computabilidade, que compreende o estudo de linguagens e a capacidade de processamento de diversos modelos computacionais, é de uma grande beleza pela simplicidade com que descreve qualquer máquina capaz de processar linguagens decidíveis. Uma tirinha que tange um pouco isso e é muito interessante é a seguinte:
http://abstrusegoose.com/261

Outra que não poderia faltar foi uma que vi recentemente sobre o irônico julgamento de Turing:
http://www.smbc-comics.com/index.php?db=comics&id=1904

Por fim, não poderia deixar de advertir que o Teorema da Parada pode acabar sendo usado como pretexto por um programador preguiçoso. Existem problemas bem simples que realmente não são computáveis, envolvendo até brincadeiras com peças infinitas de um jogo de dominó, mas essa é uma situação com a qual você se depara uma o outra vez na carreira.

Eu nunca me deparei com esse problema, mas já tive certa dificuldade em explicar para os usuários dos sistemas que trabalhei a questão sobre P=NP, um dos sete problemas de um milhão de dólares. A pergunta que surge é quase sempre a mesma: por que o sistema não encontra a solução ótima para o nosso problema decisório? E a resposta também: Porque garantir que a melhor solução foi obtida pode demorar séculos em alguns casos, e o melhor que podemos fazer hoje é encontrar uma boa solução para o seu problema em alguns minutos.

[]´s!

responder este comentário denunciar abuso
24/06/2010 - 10:56
Enviado por: Giseli

Ei, obrigada pela menção! =)

responder este comentário denunciar abuso
- 24/06/2010 - 12:21
  Enviado por: Carlos Orsi
  
  De nada, Gi! Eu que agradeço, pela lembrança…
  responder este comentário denunciar abuso
09/08/2010 - 09:13
Enviado por: Thiago Serra

Parece que surgiu uma prova séria sobre a relação de P e NP, de um pesquisador da HP:

http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/

responder este comentário denunciar abuso
- 09/08/2010 - 10:22
  Enviado por: Carlos Orsi
  
  Oi, Thiago! Sim, os links para essa prova estão se multiplicando na web… Agora é aguardar para ver se a coisa se sustenta.
  responder este comentário denunciar abuso