Just another human being
1. Números transcendentais
Um número transcendental é um número possivelmente complexo que não é raiz de *nenhum* polinômio com coeficientes inteiros. =)
2. Teorema dos quatro quadrados de Lagrange
Todo número natural pode ser escrito como a soma de quatro quadrados. TODO número natural… o.O
3. Teorema de Fermat sobre a soma de dois quadrados
Dado um número primo ímpar p, temos: p = x^2 + y^2 <=> p = 1 mod 4
PS: Arrumar um jeito pra escrever as fórmulas com a notação bonitinha.
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).
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…
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.
Minha mente me escapa. Ela tem consciência própria, vida própria, e foge. Foge do raciocínio, da lógica, da concentração. Foge de mim.
Proveniente de outra discussão sobre notícia nenhuma.
Instintos à parte, eu acredito no amor. Eles podem tentar modelar o nosso comportamento do jeito que quiserem mas eu gosto de acreditar que a gente é mais do que um monte de cadeia de carbono e interação química. Eu não tenho pesquisa nenhuma pra comprovar isso (e acho que ninguém nunca vai conseguir provar tb…), mas eu fico feliz de pensar assim. Acredito que duas pessoas podem viver juntas 50, 60 ou 70 anos por alguma coisa além do comodismo. Mesmo que as duas mudem, isso não significa que uma deixe de gostar da outra.
Além do amor, tem mais um monte de coisa que a ciência não explica, como os sonhos e os sentimentos. Eles podem fazer milhões de tomografias e descobrir váras áreas do cérebro ativadas mas a verdade é que ninguém têm uma teoria consistente a respeito dessas coisas.
Acho que se tem alguma coisa que eu acredito irracionalmente, é isso…
Eu acho que o problema todo não é a crueldade de matar bichinhos fofinhos nem se eles têm sentimento ou medo da morte. O problema é que a gente é exagerado. Precisamos de carne pra comer e acabamos matando o dobro da quantidade necessária de animais. Da mesma forma que desmatam florestas inteiras pra fazer papel e madeira (e a gente nem precisa dessas coisas pra sobreviver). Essas coisas acabam ficando exageradas porque passam a ser produção industrial. Seria completamente possível reduzir o desperdício e fazer fábricas mais sustentáveis, mas como a gente vive num mundo capitalista com pessoas ambiciosas, essa opção é em geral descartada.
Aí a gente vai culpar o sistema capitalista e exigir uma solução do governo? Na minha opinião não é bem por aí… Quem faz o sistema é a gente, e cabe a nós alterar o que achamos errado. O que uma pessoa faz pode parecer pouco, mas se vc pensar no impacto que isso tem se um milhão de pessoas mudarem seus hábitos, a gente realmente pode fazer uma diferença considerável. Eu não sou forte o suficiente pra cortar carne completamente da minha dieta, mas eu posso muito bem diminuir o consumo e o desperdício de comida. Da mesma maneira que eu posso usar folhas de rascunho e mandar o papel pra reciclagem pra diminuir o número de árvores cortadas.
Eu não estudei economia e não sei que tipo de consequência isso vai gerar pras grandes indústrias, e se elas vão parar de ser irracionais ou não. Algumas pessoas defendem que sim, outras defendem que é preciso de uma ação do governo e tal. Como eu não pretendo seguir carreira política ou nada próximo, eu acredito no primeiro grupo e tento fazer minha parte.
“Se não trabalhar sempre, se não ocupar todos os minutos, quem sabe de que será capaz a mulher? Quem pode vigiar os sonhos de moça? [..] Portanto, é impedir que se formem. A total ocupação varre o espírito.”
Ou não, não se deve impedir os sonhos.
If something can be computed in lambda-calculus, it can be computed. But lambda-calculus is not implementable because it is non-deteministic and computations may not terminate. It is non-deterministic because it doesn’t have a rule for the order in which reductions are applied. Sometimes the same term can have an infinite reduction and a terminating one, depending on the order in which things are done. That’s why we should study other possible calculi to implement. It would be nice to have termination garantees. When a calculus has this property we say that it is strong normalizing (all the derivations terminates). It may also be weak normalizing, meaning that some derivation terminates. The name comes from the fact that a derivation (computation, sequence of reductions) terminates when it reaches a normal form. So, there is the need to define what is a normal form of the calculus. It is important as well to garantee that, if a term has two or more derivations, these should all end up in the same normal form (somewhere during the derivation terms get together again). That is called the confluence property. Therefore, a calculus should also be confluent because we don’t like inconsistencies.
One of the forms of garanteeing normalization could be to define an order in which the reduction rules are applied.
Rewriting systems are systems formed with rules that tells you how things can be rewritten. For example:
s(0) -> 1
s(x + y) -> x + s(y)
So we could say that the lambda-calculus with its beta-reduction is a rewriting system. Actually, I might say that all calculi are rewriting systems. These systems can also define computations depending on the way terms ans rules are defined. They are also worried with termination and confluency.
(Maybe not that organized…)