Theoretical Computer Science

Pessoal que gosta de teoria, uni-vos!

Não sei exatamente como a coisa funciona, mas estão querendo criar um site pra discutir coisas de teoria da computação no mesmo estilo que o Stack Overflow.

Só que pro site entrar no ar, tem que passar por umas fases de definição e ter uma certa quantidade de pessoas interessadas... Participem ou pelo menos ajudem a divulgar =)

Tem um "referrer" na URL e não sabia o que eu ganho com isso. Fui verificar e descobri que ganho "pontos de reputação"... sejá lá a utilidade disso.

O problema da parada

Hoje estava lendo sobre o Problema da Parada e percebi um pouco mais a profundidade desse resultado, a partir de alguns exemplos. Resolvi escrever aqui sobre ele. Para quem não conhece o problema, ele pode ser encarado da seguinte forma:

Problema da Parada

Entrada: um programa "P" com sua respectiva entrada "E".

Saída: Sim, se o programa "P" para de rodar com a entrada "E". Não, caso contrário.

Em outras palavras, dado um programa, você quer saber se ele para de rodar ou não. Pra descobrir isso, você precisa de um outro programa. Mas, como Alan Turing mostrou, não existe um programa que resolva o Problema da Parada. Não vou entrar na argumentação de porque ele não existe, mas sim em uma outra coisa que nunca havia me dado conta, de quão importante é esse resultado.

Considere, por exemplo, o Último Teorema de Fermat. Caso existisse um programa que resolvesse o problema da parada, teríamos uma prova quase trivial para o Último Teorema de Fermat. Considere o programa P abaixo:

Programa P

Para toda tripla (x, y, n) de inteiros, x > 0, y > 0, n > 2.

Verifique se existe z inteiro satisfazendo:

Se existe z, pare.

Note que esse programa só parará de rodar caso exista um contra-exemplo para o Último Teorema de Fermat. Portanto, utilizando a solução do Problema da Parada com o programa P como entrada, teríamos como verificar a validade do Último Teorema de Fermat. Da mesma forma, esse mesmo argumento poderia ser utilizado para provar (ou refutar) diversas conjecturas e resultados por aí.

Claro que, mesmo se existisse, a solução para o Problema da Parada poderia ser ineficiente, ou seja, poderia ser necessário muito tempo para que o programa rodasse e uma resposta fosse dada. Mas esse tempo ainda seria finito e, portanto, podemos praticamente afirmar que seria apenas uma "questão de tempo" até termos uma resposta. Note que o programa P serviria para refutar o Último Teorema de Fermat caso ele não fosse verdadeiro mas, por outro lado, apenas com ele, nunca poderíamos ter certeza de que o teorema é verdadeiro, pois nesse caso ele teria que testar uma infinidade de triplas e, portanto, nunca pararia. Assim, de fato, a solução do Problema da Parada seria um resultado importantíssimo.

Exame de qualificação

Semana que vem, dia 22, às 10:00, ocorrerá meu exame de qualificação. É um passo acadêmico e burocrático do doutorado, onde você deve apresentar para uma banca aquilo que você fez e aquilo que pretende fazer no restante do doutorado. Na banca, além do meu orientador, Jayme Szwarcfiter (já digito sem ter que copiar!), estarão também o professor Valmir Barbosa, um (excelente) professor titular da Coppe, UFRJ, e o professor Eduardo Laber, da PUC-Rio.

Normalmente o exame de qualificação ocorre no meio do doutorado, ou seja, depois de 2 anos de ingresso, mas, no meu caso, acabou tendo que ser diferente. O Jayme tem um projeto de pesquisa com uma universidade da Alemanha, que prevê, dentre outras coisas, bolsas de doutorado sanduíche. Assim, surgiu a possibilidade de passar um tempinho lá. Devido ao calendário acadêmico alemão, seria interessante que eu fosse em outubro próximo. Assim, acabei tendo que correr pra defender o exame de qualificação mais cedo, com apenas 1 ano de doutorado. A parte boa é que isso acabou imprimindo um ritmo mais intenso no doutorado, que me impede de procrastinar como de costume ;-)

Agora é correr pra conseguir fazer tudo certo e a tempo pra conseguir satisfazer o calendário da burocracia da Capes e não ter que adiar a viagem.