Sobre funções computáveis

The most amazin fact: “All the attempts at formalizing the intuitive notion of computable function yield exactly the same class of functions.” [1]

Paradigma 1: Máquina de Turing
– Possui uma fita dividida em quadrados (potencilamente infinita – pode ser estendida para a direita ou esquerda quando necessário).
– Possui uma cabeça de leitura que observa um quadrado, lê ou escreve algo no quadrado corrente ou se move para um dos quadrados vizinhos.
– Cada quadrado pode conter um símbolo (1) ou estar vazio (0).
– Operações básicas:
  1. Escreve o símbolo 1 no quadrado corrente.
  2. Apaga o símbolo que ocorre no quadrado corrente.
  3. Move para o quadrado à direita.
  4. Move para o quadrado à esquerda.

Paradigma 2
: Função recursiva primitiva
– Todas as funções computáveis são resultado da aplicação de duas operações básicas em três funções básicas que são obviamente computáveis.
– Funções iniciais:
  1. Z(n) = 0 –> zero
  2. S(n) = sucessor de n na sequência de números naturais –> sucessor
  3. P(i,k) (x1, x2, …, xk) = xi –> projeção
– Operações básicas:
  1. Composição de funções
  2. Recursão primitiva:
      * para funções de uma variável: f(0) = d
                                                          f(n+1) = h( f(n), n )
      * para funções de mais de uma variável: f(0, x1, x2, … xk) = g(x1, x2, … xk)
                                                                        f(n+1, x1, x2, … xk) = h( f(n, x1, x2, … xk), n, x1, x2, … xk )

Dentre outros paradigmas…
Bacana pensar que essas duas definições super diferentes (uma bem operacional e outra bem matemática) vão resultar na mesma classe de funções. Isso pode ser um indicativo que eles estão na direção certa (se é que existe uma direção natural pré-definida pra seguir).

[1] Computability 3ed. Epstein, R. L. and Carnielli, W. A.

Sobre P = NP

Estava lendo esses dias esse artigo aqui da ACM sobre o estado atual da arte na tentativa de provar se P é igual ou diferente de NP, e algumas observações me fizeram perceber algo que não tinha reparado antes.

Todos nós sabemos que a segurança da criptografia de chave pública (utilizada para transferir dados de modo seguro por uma rede de computadores) se baseia fortemente na dificuldade de fatorar números grandes em primos (também grandes). E existe toda a lenda de que se alguém provar que P=NP, toda a segurança vai por água abaixo, o que nos leva a supor que o problema de fatorar números seja NP-completo. Entretanto, no artigo citado o autor afirma que não se sabe se esse problema é NP e acredita-se realmente que ele não seja. Então eu me pergunto porque existe esse alarde todo sobre a segurança da criptografia quando se fala sobre P = NP. Tá faltando alguma coisa… se P for igual a NP significaria que todos os problemas poderiam ser resolvidos em tempo polinomial? Até aqueles que não se sabe a que classe pertencem?

Eu to perdendo algum detalhe…

Sobre sacolinhas plásticas

Durante uma discussão na grad se a atitude de não usar sacolinhas plásticas é válida ou não para ajudar a resolver o problema do meio ambiente, surgiu o argumento que na verdade o problema está na população mundial que não pára de crescer. Então fui pesquisar sobre o crescimento da população e descobri que ele têm diminuído. Talvez ele seja negativo um dia, mas isso não é motivo pra eu parar de tentar ser ecologicamente correta. Afinal de contas, eu gostaria que o mundo melhorasse dentro dos próximos 10 ou 20 anos, quando ainda estarei aqui lúcida (assim eu espero!).

Enfim, o mais legal foi que eu achei isso aqui: http://esa.un.org/unpp/index.asp?panel=2
Com um monte de dados de um monte de países, ou continentes ou o mundo todo.