It’s Evolution, Baby!

Durante a tradicional apresentação inicial sobre Open Source e Software Livre que o CInLUG faz pros calouros das computações, alguém me perguntou: “mas esses softwares (livres) nunca estão prontos, eles devem ter muitos defeitos, não é?”. A resposta era fácil e estava na ponta da língua antes dele terminar de falar, mesmo assim me permiti pensar algumas coisas por uma fração de segundo tão longa que a sala parecia uma imagem em pausa. “Rapaz, a VIDA é cheia de defeitos!”, eu disse enquanto fazia uma macaquice de alguém tendo algum tipo de epilepsia/tique-nervoso. Imagino que foi uma piada bem contada, porque todos riram muito, e porque eu não ri junto, o que acabaria estragando a seriedade da anedota. E era uma piada muito séria.

Que todo mundo é diferente você já sabia (espero), mas já se perguntou o quão diferente?

Os lingüistas dizem, ou pelo menos o Anthony Burguess diz no excelente livro A Literatura Inglesa, mas ele não é lingüista. Onde estava? Ah, alguém disse, talvez não exatamente isso, mas algo parecido… Retomando – um idioma é criado quando o dialeto, de um grupo de dialetos semelhantes, usado pelo grupo mais poderoso, é eleito como o idioma oficial pela força político-militar desse mesmo grupo. Em outras palavras, o que chamamos de idioma de uma nação é uma colcha de retalhos de dialetos.

Com as pessoas, ou melhor com os genes delas, é a mesma coisa: humanidade é um conceito baseado num número de semelhanças maior que o número de diferenças, é a “normalidade estatística”. (Normalidade é uma questão numérica, por isso ninguém é cego nas profundezas abissais.) No geral somos (nós humanos) muito parecidos por fora, apesar de uma ou outra diferença.

Polidactilia

Essas alterações acontecem por conta de erros de cópia dos genes, por causa de radiação cósmica, e, claro, por culpa dos videogames e desenhos de pokémons.

As mutações físicas sempre chamam atenção, muitas delas tornam o indivíduo inapto pra sobreviver. A natureza é uma mãe psicótica sempre tentando matar seus filhos, ou pelo menos os que dão mais trabalho. Como de costume, é pro seu próprio bem.

Mutação e Seleção

O básico de evolução é: mutações aleatórias geram diversidade, seleção natural diminui a diversidade.

Observe que todos os gigantes de duas cabeças, cíclopes, centauros e fadas estão representados pelas bolinhas com “X” vermelho.

E mesmo o que encontramos por aí está longe de ser perfeito. Dê uma olhada nesse vídeo apresentando um “robô gafanhoto”, dê uma olhada como o gafanhoto orgânico quase cai de costas durante um pulo. Um design porcaria (o robôzinho logo deve estar fazendo melhor), mas que funciona bem o bastante.

Está Tudo na Sua Cabeça

Com o desenvolvimento da nossa venerável linhagem humana com seus corpos cada vez mais pelados e unhas de maricas, mutações mais interessantes começaram a acontecer onde não podiam ser vistas – no cérebro. Mas os efeitos das mutações podiam ser sentidos: você não precisa ter garras de tigre, ou ser grande como um tiranossauro (o que é bem caro de se manter), basta ser esperto. Fácil? Nem a pau! Com grandes cérebros vêm grandes dores de cabeça.

Algumas mutações no cérebro devem ter gerado todo tipo de doido, pior ainda se desapercebidamente ele se torna o líder do grupo. “Vamos todos nos matar pra subir na nave escondida atrás do cometa!” Parabéns! Felizmente a maioria dos doidos acabou se matando antes (Darwin Awards!) e levando sua linhagem condenada pro esquecimento genético.

Ou não?

Havia uma matéria na NewScientist (a assinatura foi uma grande idéia INdT!) de um mês que não lembro (desculpem por essa), que perguntava: se a seleção natural diminui a variedade, não deveríamos todos ser mais parecidos em comportamento e ter o mesmo temperamento? (É, esse seu gênio ruim é hereditário!) Cientistas observaram alguns grupos animais, algum pássaro (que não lembro), haviam indivíduos mais ousados que iam muito longe da área familiar do grupo, e outros que não gostavam tanto de sair de casa. Por quê com o tempo e intempéries e predadores não restou só o grupo mais caseiro?

Por que as coisas mudam. As coisas mudam o tempo todo.

Em épocas de vacas gordas, ficar em casa é uma boa. A geladeira está cheia, nenhum predador a vista, a vida é sexo, relaxar, sexo, comer, alguma coisa que pássaros fazem, sexo… Os mais saídinhos acabam tendo mais chances de se perder, morrer de fome ou virarem comida.

Aí vem o tempo das vacas magras. Um cometa caiu, um vulcão explodiu, qualquer coisa. Aqueles pássaros mutates (pra mim todo indivíduo é um mutante) com firmware de ficar em casa, vão ficar com aqueles sentimento “vai ficar tudo bem, passa logo, vou sentar aqui e esperar”, enquanto o mundo desaba. Os mais ousados e pirados só estavam esperando uma desculpa pra se mandar, eles terão o impulso natural de explorar e eventualmente achar um lugar melhor pra viver. O que não é difícil se a antiga área de morada virou um inferno de predadores famintos, fogo, enxofre e pagodeiros.

E assim a variedade de comportamentos dentro de uma mesma espécies é justificada pela utilidade que varia com o tempo e as mudanças de condição ambiental.

Caçadores e Coletores (que soa melhor que Catadores)

Antes da agricultura e da televisão, os humanos não paravam muito em casa, pelo menos não os homens. O grupo se fixava em algum lugar seguro, as mulheres ficavam com as crianças e os homens saíam pra caçar. Grandes caçadas podiam durar dias. Dizem que no tempo em casa as mulheres tinham tempo fazer observações mais detalhatas da natureza, como o crescimento das plantas, mudanças ambientais, e assim inventariam a agricultura. Quem inventaria a novela televisiva ainda não sei.

A caçada era uma coisa muito séria e tudo dependia dela. Força física era importante, e provavelmente todos os caçadores tinham o mínimo que a tarefa exigia, e quem não se enquadrasse teria o direito democrático de morrer. Mas como sabemos força não é o que torna os humanos (e parentes) especiais, características cerebrais como persistência, coragem, inteligência é que aumentavam a quantidade de caça levada pra casa.

Não seria surpreendente se aparecesse uma mutação que se encaixasse nesse estilo de vida.

Ascenção e Queda dos Caçadores Hiperativos

Descobri uma palavra interessante faz um tempo: Neurodiversidade. É uma forma de encarar algo que de outra maneira seria chamado deficiência mental, o que além de soar mal, não traduz muito bem a realidade. Como vimos no caso dos passarinhos caseiros e ousados, a neurodiversidade deles foi fundamental para sobrevivência da espécie às mudanças. É dito que a neurodiversidade é tão importante para uma espécie quanto a biodiversidade é importante para a vida em geral.

Existem várias condições cerebrais que poderíamos usar como exemplo, mas por um motivo arbitrário vou pegar aquela conhecida como Transtorno de Défcit de Atenção com Hiperatividade (e mais outros tantos nomes). O conhecimento sobre essa condição é relativamente recente, no começo sendo atribuída a problemas de caráter e criação, mas agora sabe-se que tem causas genéticas.

Como bem sabemos, não fosse uma característica útil não teria ajudado seu portador, e se fosse danosa o teria levado pra um caminho sem volta. Pensando nisso um cara chamado Thom Hartmann propôs a teoria dos Caçadores vs. Fazendeiros. Que é mais um esboço de uma teoria, uma hipótese ainda não verificada, mas com um bom fundamento e que já começa a ser estudada.

Mas primeiro algumas características dos portadores de TDAH (bem por cima, na wikipédia tem mais informações; eu também não faço diagnósticos, vá procurar uma médica se desconfia de algo; e não é verdade que todos são sexy, não tire por mim):

  • impaciência com tarefas chatas
  • impulsividade
  • inquietação física
  • sensação de estar sempre “na correria”
  • distração

E tem uma coisa extra, o tal do hiperfoco, que apesar do nome, não chega a ser um super-poder de quadrinhos, mas ainda assim é uma viagem. Apesar dos problemas em manter a atenção em tarefas regulares, quando está fazendo algo que considere estimulante o sujeito com TDAH pode passar muito tempo sem pensar em outra coisa, dirigir todos os esforços pra realizar a tarefa. Uma pena que nem sempre o que ele quer fazer é o que ele deve fazer, fato que no começo, juntanto as outras caraceterísticas, me fez pensar que TDAH era um bom disfarce pra preguiçosos e safados.

Programar pode ser estimulante pra uns (passei uns dias programando um negócio sem nem conseguir articular verbalmente o que estava fazendo, eu não queria parar; tinha um prazer estranho na atividade, dizem que os esportistas sentem isso) (percebi que faço parênteses grandes…), mas correr pelo mato atrás de um bicho selvagem deve ser o tipo de coisa que prende a atenção de alguém. Não essa porcaria de maricas ingleses caçando uma pobre raposa, mas correr como um louco com seu coração pra explodir e com sua vida dependendo disso. Ainda não inventaram videogame melhor isso.

As características de inquietação, distração e impaciência, como nos pássaros do exemplo anterior, compeliriam o caçador à perambular, aumentando as chances de localizar caça. Enquanto em movimento não sua atenção iria de um lado para outro, nunca se fixando por tempo demais numa bobeira qualquer, e finalmente quando aparecesse o jantar sobre quatro patas, o hiperfoco tomava conta, e nada mais existia exceto um futuro animal morto que insistia em correr. E o simples prazer de fazer isso.

Esses caçadores eficientes (e não super-caçadores, note bem) tinham mais chance de trazer comida, logo, viviam bem e saudáveis, logo, pegavam mais mulheres. Era uma época interessante, e os genes que carregavam essa característica deviam ser populares. Então no Neolítico surge a agricultura, mas essa não seria a “mudança de paradigma” que “colocaria todos os caçadores na rua”. O Downsizing só surgiria milhares de anos depois.

Aldeia do Neol�tico

A transição levou uma quantidade de anos com quatro dígitos, e a caça ainda estava em alta, tanto por motivos práticos quanto de status social, o que possivelmente dava aos nossos caçadores hiperativos licença pra terem suas esquisitices. E essa é minha deixa pra ir pro lado ruim da coisa.

Pelo que sabemos de evolução, a condição que chamamos hoje de TDAH não apareceu prontinha numa caixa com um rótulo e um logotipo da Umbrella Corporation (também conhecida no mundo real como Monsanto). A coisa simplesmente aconteceu, a natureza não decidiu que teria um tipo de humano bom em caçadas, foi só um cérebro não muito bem copiado (como um download estragado e sem verificação de md5) que calhou de produzir umas características boas. Contudo, outras coisas não foram tão bem.

Cérebros Normal e TDAH

A imagem acima mostra a atividade cerebral de uma pessoa estatísticamente normal, e outra com caso (muito, note bem, muito!) severo de TDAH. Os maiores défcits ocorrem no córtex pré-frontal superior (ex: orientação à objetivos, controle de comportamento social) e córtex pré-motor (ex: um tipo de função motoras que você vai saber indo na wikipedia).

Em outras palavras, a coleção de características do caçador hiperativo é resultado do fato de o bit que liga a chave de energia de dois brinquedos do parquinho estar levemente em 0 (digo “levemente” porque deve ser um qubit, o cérebro deve ser um computador quântico :P). Assim, a condição de TDAH vem inteiramente grátis com o que os médicos chamam de comorbidades, que são distúrbios secundários associados, e inteiramente opcionais – pode-se ter nenhuma, uma ou várias, e podem ser versões mais brandas do que nas pessoas que tem esses transtornos como desordem primária em seus cerebrozinhos. (Na verdade todos devem ter algo desses transtornos em níveis mais baixos, afinal, somos todos uma grande família.) Algumas comorbidades: Transtorno Desafiador Opositor (fãs do Rage Against The Machine), Abuso de Substâncias, Depressão, Humor Bipolar, Ansiedade, Tiques.

Voltando à evolução, da espécie e do problema, segundo a hipótese que estamos debulhando, os hiperativos contribuíram imensamente nos primórdios da espécie humana, continuaram úteis no início da agricultura, até suas vantagens se tornarem pouco relevantes para a espécie como um todo. E à medida que a sociedade se organizava, esses desordeiros se viam mais e mais deslocados; os comportamentos disfuncionais mascarados pelo estilo de vida primitivo começaram a vir à tona. E a coisa só piorou com o aumento da organização social e das expectativas de responsabilidade, confiabilidade, e outros *-dades.

E agora?

E agora perdi o fio da meada. Estava ruminando essas idéia faz um bom tempo, mas não conseguia organizar tudo. Daí uma hiperfocadazinha e um pequeno distúrbio de sono e pronto, feito o serviço. (Mas nem fudendo que vou fazer uma revisão nisso tudo agora.)

Desde que soube da minha condição (por causa dos problemas de vida decorrentes), provavelmente passei por alguma lista de fases clássicas (negação, raiva, etecetera), mas quando descobri que existia uma explicação dos motivos de se nascer desse ou de outro jeito a coisa melhorou bastante. Quero dizer, além de uma boa história é uma explicação muuuito melhor do que “é porque Deus me odeia”.

De fato me sinto até parte de algo útil é bom saber que além de crianças com o dobro de membros e vacas 2 cabeças de Chernobyl, essas mutações podem trazer novidades interessantes. Outro dia assisti no SeuTubo um documentário do canal discovery sobre geneticistas que querem isolar mutações benéficas raras e possívelmente colocá-las nas próximas gerações. Os mutantes em questão eram: um cara que pode subir a temperatura corporal com o pensamento e assim resistir a temperaturas baixíssimas por muito tempo; uma moça com sinestesia, que é a fusão de percepções, e que fazia ela ver cores e sentir gostos associados aos sons (considero isso muito útil pra determinar categoricamente que existe péssimo gosto musical; imagine a coitada vomitando num “show” do créu); um cara que podia fazer cálculos enormes, sem ser autista; e um pintor cego (ele nasceu sem olhos) capaz de fazer perspectivas. O nome do vídeo é The Real Superhumans, e acabei de ver que a versão completa foi tirada do SeuTubo por questões de direitos autorais. Sugiro que procure em algum outro lugar.

Genetic Fashion Week

Por um lado é legal que possamos multiplicar “genes bons” pras próximas gerações, por outro corremos os risco de decidir o que é bom e o que é ruim baseado na moda da semana. Se pudéssemos escolher amanhã como seriam nossos filhos, a chapinha seria extinta numa geração porque todo mundo teria cabelos lisos, possivelmente olhos azuis e não menos que 1,80m de altura. E, é claro, um pirocão desse tamanho! Um Q.I. enorme também seria bom pra aprender a julgar o que é sensato, mas opa, inteligência não é o mesmo que sabedoria (como sabe qualquer jogador de D&D), e isso não é genético.

Outra coisa que as modinhas podem fazer é extinguir “genes obsoletos”. Mas como saber que algo não vai ser útil depois. Se o estabilishment dos pássaros que não saem de casa extinguisse o gene dos porraloucas aventureiros e mais tarde isso se tornasse necessário pra sobrevivência da espécie? Como que ficava? Não ficava, oras.

Então quando perder a paciência com seu amiguinho TDAH (ou autista, ou bipolar, ou com síndrome de Tourette, ou Emo) respire e repita o mantra: Neurodiversidade é tão boa para espécie quanto a biodiversidade é para vida.

Agora, o irônico mesmo dessa hipótese do cérebro de caçador é o fato de eu ser vegetariano…

Máquinas de Turing São Dispositivos de Manipulação Simbólica

Foi uma surpresa quando descobri isso. Vinha estudando autômatos determinísticos, não-determinísticos e de pilha, que são capazes de reconhecer linguagens. Estava só esperando a hora de chegar na Máquina de Turing e descobrir se ela fazia algo mais próximo da lógica, como usar portas AND, OR, etc, mas nada disso, ela continuava sendo uma manipuladora de linguagens. Foi daí que começou a viagem…

A Máquina de Turing

Foi uma grande sacada de Alan Turing descrever computação através de uma máquina hipótetica, relativamente simples e com um funcionamento bem fácil de entender.

Primeiro sua estrutura “física”. Temos uma cabeça de leitura e escrita, onde está armazenada a função de transição, uma fita onde a cabeça fará suas operações. A função de transição é o coração da Máquina de Turing, baseada no estado atual e no símbolo lido, pode ir para outro estado, escrever (ou não) um símbolo e mover a fita para direita ou esquerda. A computação termina se a máquina chegar num estado de aceitação ou rejeição, mas pode acontecer da máquina de turing ficar rodando para sempre, sem nunca chegar numa solução.

Máquina de Turing
Concepção artística de uma Máquina de Turing

A Máquina de Turing é uma abstração para qualquer computação possível, é a “encarnação” de um algoritmo.

Equivalência

Ao pensar numa computação usando uma fita como memória, indo pra frente e para trás, lendo e escrevendo… dá pra imaginar que levaria um milhão de anos pra calcular os gráficos pra uma cena de Shrek. E levaria mesmo! Mas, para encurtar o tempo, poderíamos colocar duas fitas: no lugar de escrever algo no começo, andar até bem longe, ler alguma coisa, voltar, ir de novo, etc, poderíamos ir bem mais rápido com duas fitas e duas cabeças de leitura. Contudo, uma máquina de uma fita chegaria no mesmo resultado. Podíamos ainda trocar a fita por memórias de silício e armazenar a função de transição num novíssimo processador multi-core. Melhor ainda: numa fazenda de renderização! Assim o filme saíria em tempo.

Não importa como implementemos o computador, ele sempre poderá ser reduzido a uma Máquina de Turing básica. Por isso é dito que nenhum dispositivo computacional tem poder maior que uma Máquina de Turing.

Poder != velocidade. Poder computacional diz que coisas um dispositivo é capaz de computar, os autômatos finitos tinham um poder muito menor que a Máquina de Turing. Se um problema pode ser resolvido em tempo finito, mesmo que longo, o tempo pode ser encurtado com dispositivos computacionais mais velozes; se o problema não pode ser resolvido em tempo finito, bem, o infinito não pode ser encurtado, e você entrou na Terra dos Problemas Não-Computáveis.

Computação (Sintaxe) X Pensamento (Semântica)

Pode-se criar uma máquina de turing que faça uma operação AND, mas ela não vai saber que está fazendo uma operação AND. Computadores são capazes de manipulação simbólica, ou seja de elementos sintáticos, mas são as mentes humanas que atribuem significado à computação realizada.

Agora seja um bot bonzinho e siga esse link pro argumento do Quarto Chinês, mesmo que você não compreenda.

Update: alguém me dê esse livro.

Update2: outro ponto de vista: Dresden Codak. Adoro esse negócio, uma pena que a produção seja tão lenta.

Simulador de Máquina de Turing com PyGame

Implementar Máquinas de Turing em python é interessante, mas visualmente a coisa não empolga pra quem não é o progrador. Daí, com estas mãos, este cérebro e PyGame, fiz um simulador visual de Máquina de Turing, onde você pode ver a fitinha indo hipnoticamente pra lá e pra cá.

Para usar o simulador, pegue o arquivo tmsim.tar.gz, descompacte-o, entre no diretório tmsim e execute ./simulator.py

Para quem é preguiçoso ou impaciente, fiz um screencast usando Istanbul.

A função de transição que está rolando no vídeo realiza uma operação AND entre duas strings binárias (1010111 e 1100100) e escreve o resultado após o símbolo “#”. Os caracteres das strings estão escritos alternadamente na fita, de forma que abcd & ABCD aparecem na fita como aAbBcCdD#.

Segue o grafo da função de transição.

Máquina de Turing - AND

Máquina de Turing

Foi uma grande sacada de Alan Turing descrever o que é uma computação através de uma máquina hipótetica, simples à primeira vista, e com um funcionamento bem fácil de entender.

Vejamos sua estrutura “física”. Temos uma cabeça de leitura e escrita, uma fita onde a cabeça fará suas operações, e em algum lugar está armazenada a função de transição. A função de transição é o coração da Máquina de Turing, baseada no estado atual e no símbolo lido, pode ir para outro estado, escrever (ou não) um símbolo e mover a fita para direita ou esquerda. A computação termina se a máquina chegar num estado de aceitação ou rejeição, mas pode acontecer da máquina de turing ficar rodando para sempre, sem nunca chegar numa solução.

Tenha em mente que a Máquina de Turing é uma abstração para qualquer computação possível, é a “encarnação” de um algoritmo, e o que vale pra ela vale pra um supercomputador multicore dos dias de hoje.

Máquina de Turing
Concepção artística de uma Máquina de Turing

Formalmente a Máquina de Turing é descrita dessa forma:

MT = (Q, Σ, Γ, δ, s, q_aceita, q_rejeita)

  • Q: estados da máquina;
  • Σ: alfabeto de entrada, ou seja, os caracteres usados para formar as strings processadas pela máquina;
  • Γ: alfabeto da máquina, contém os caracteres do alfabeto de entrada mais caracteres extras que a máquina pode escrever na fita;
  • δ: função de transição, diz qual símbolo deve ser escrito na fita, para que lado esta deve ser movimentada e para qual estado a máquina deve ir, baseado no estado atual e no símbolo (ou caractere) lido na entrada; esta é a programação da Máquina de Turing;
  • s: estado inicial;
  • q_aceita: se o processamento terminar nesse estado, a string é aceita como válida pela máquina;
  • q_rejeita: se o processamento terminar nesse estado, a string é rejeitada pela máquina;

A descrição da função de transição é particularmente verbosa, normalmente o diagrama de uma máquina de estados é usado em lugar de uma descrição textual.

Máquina de Turing - Função de Transição

A seta de q5 para q6 representa uma transição e significa: se o símbolo lido da fita for “0″ ou “1″, escreva “x” e mova a fita para direita (R); a transição de q6 para q6, significa: se ler “x”, não escreva nada e se mova para esquerda (L).

Equivalência

Ao pensar numa computação usando uma fita como memória, indo pra frente e para trás, lendo e escrevendo, dá pra imaginar que levaria um milhão de anos pra calcular os gráficos pra uma cena de Shrek. E levaria mesmo! Para encurtar o tempo poderíamos colocar duas fitas: no lugar de escrever algo no começo, andar até bem longe, ler alguma coisa, voltar, ir de novo, etc, poderíamos ir bem mais rápido com duas fitas e duas cabeças de leitura. Contudo, uma máquina de uma fita chegaria no mesmo resultado. Podíamos ainda trocar a fita por memórias de silício e fazer um novíssimo processador multi-core processar a função de transição, que aliás seria escrita numa linguagem de altíssimo nível, pra aumentar a produtividade.

Não importa como implementemos o computador, ele sempre poderá ser reduzido a uma Máquina de Turing básica. Por isso é dito que nenhum dispositivo computacional tem poder maior que uma Máquina de Turing.

Poder != velocidade. Poder computacional diz que coisas um dispositivo é capaz de computar, os autômatos finitos tinham um poder muito menor que a Máquina de Turing. Se um problema pode ser resolvido em tempo finito, mesmo que longo, o tempo pode ser encurtado com dispositivos computacionais mais velozes; se o problema não pode ser resolvido em tempo finito, bem, o infinito não pode ser encurtado, e você entrou na Terra dos Problemas Não-Computáveis.

Implementação em Python

A representação da Máquina de Turing em python ficou bem parecida com aquela do Autômato Finito Determinístico (AFD) de um post anterior. Assim como para o AFD, criei um método para gerar o grafo da função de transição, o que ajuda muito na hora de saber se as transições codificadas são mesmo as que você projetou.

Foi criada uma classe TuringMachine, com atributos correlatos à definição formal dada acima. Exceto que o atributo para o alfabeto da máquina não contém o alfabeto de input, os dois alfabetos são concatenados no momento de usar.

A função de transição para o trecho de diagrama dado acima:

trans_func = {
'q5': {'0': ('q6', 'x', TuringMachine.RIGHT),
'1': ('q6', 'x', TuringMachine.RIGHT),},
'q6': {'x': ('q6', None, TuringMachine.LEFT)}
}

O resultado da transição é acessado assim: trans_func['q6']['x']. E o resultado é uma tripla ('q6', None, TuringMachine.LEFT), que representa o próximo estado, o símbolo a ser escrito, e para qual lado movimentar a fita. Para abreviar a definição, se uma transição estiver definida o próximo estado será o de rejeição e a máquina pára.

O código da máquina está em:

Se for executado da linha de comando, será chamada uma função de teste que implementa uma máquina que verifica se a string dada faz parte da linguagem {w#w|w ϵ {0, 1}*}, ou seja, se a string antes do símbolo “#” é igual a string que vem depois, ou seja (novamente), strcmp.

Abaixo o diagrama da função de transição, gerado automaticamente e renderizado para SVG pelo Graphviz.

Máquina de Turing - {w#w|w ϵ {0, 1}*}

<referênciaLiterária>Espero que essa implementação seja mais conveniente que aquela encontrada no Castelo do Duque de Turing.</referênciaLiterária>

Gerando Grafos de Automatos Finitos

Acrescentei uma função para gerar grafos no formato DOT dos autômatos finitos determinísticos usados naquele programa do meu último post sobre autômatos. Com isso tenho uma implementação que funciona mais uma visualização decente.

A função de geração é mostrada a seguir. Perdoe usar pontos como identação, é que o wordpress (sem plugins) foi amaldiçoado por um programador corcunda de COBOL com a incapacidade de indentar. O código decente pode ser visto em automato.py

def generate_graph(trans_func, start_state, final_states):
....states = trans_func.keys()
....states.sort()
....dot_graph = 'digraph finite_state_machine {\n'
....dot_graph += ' rankdir=LR;\n'
....dot_graph += ' edge [fontname=arial,fontsize=11]\n'
....dot_graph += ' node [fontname=arial,fontsize=11,shape=doublecircle];'
....dot_graph += ' '.join(final_states)
....dot_graph += ';\n'
....dot_graph += ' node [shape=circle,size=8]\n'
....dot_graph += ' start [shape=point]\n'
....dot_graph += ' start -> %s\n' % start_state
....for state in states:
........values = trans_func[state].keys()
........values.sort()
........for value in values:
............dot_graph += ' %s -> %s [label=%s]\n' % \
....................(state, trans_func[state][value], value)
....dot_graph += '}\n'
....return dot_graph

(Queria ter colocado “Bitstream Vera Sans” no lugar de “Arial” como fonte, mas por motivos além da minha vontade estou num windão.)

O autômato no formato DOT é visto abaixo. Para fazer a seta que indica o estado inicial e que não parte de nenhum dos nós usei shape=point no nó start, cujo nome nem aparece por causa da forma escolhida.

digraph finite_state_machine {
....rankdir=LR;
....edge [fontname=arial,fontsize=11]
....node [fontname=arial,fontsize=11,shape=doublecircle];q1;
....node [shape=circle,size=8]
....start [shape=point]
....start -> q1
....q1 -> q1 [label=0]
....q1 -> q2 [label=1]
....q2 -> q1 [label=0]
....q2 -> q2 [label=1]
}

Tentei gerar um png mas saiu muito feio, cheio de rebarbas, a imagem abaixo foi gerada a partir do SVG gerado pelo dot (com o comando: dot -T svg -o afd.svg afd.dot).

AFD

Nota: para usar o dot é preciso instalar o pacote graphviz num sistema Debian/Ubuntu; se por algum motivo estranho você estiver no Windows pegue o GraphViz aqui.

Automatos Finitos em Python

Seu computador computa, sua calculadora computa, uma flor computa, você computa, enfim, o universo inteiro computa. Uma verdadeira computaria.

Se encararmos qualquer estado (apagado, aceso, em movimento, triste, com fome) como informação, todo processo que altera esse estado, altera também a informação. Ou melhor, processa a informação, atividade comumente atribuída aos computadores, mas que é feita pelo universo desde que… desde de sempre! (Se é só isso que o universo faz, aí é outra história.)

Pra saber se alguma máquina de computação estava computando direito ou ainda qual seria seu poder computacional, um modelo matemático formal que dissesse “isso aqui é uma computação” era necessário. O modelo que usamos hoje é a máquina de turing, e seu criador, Alan Turing, foi recompensado por essa contribuição sendo levado (dizem alguns) à morte. Mas estou dispersando, isso também é outra história.

Não vou falar aqui da máquina de turing (ainda não cheguei nela em Informática Teórica), e sim de Autômatos Finitos Determinísticos (AFDs pra encurtar). Trata-se de uma máquina mais simples com propósito restrito: determinar se uma string de entrada é parte de uma dada linguagem ou não.

Uma explicação mais elaborada sobre linguagens (no contexto computacional) pode ser encontrada na entrada “Linguagem Formal“, na Wikipedia, no entanto darei alguns exemplos. Usando o alfabeto (os símbolos possíveis da linguagem) {0, 1}, podemos ter a linguagem composta das strings que começam com “110″ e terminam com qualquer coisa; a linguagem das strings que terminam em “0″; ou a linguagem das strings que possuem a substring “10101″.

Se fossem nomes de arquivos no unix, poderíamos listar os membros das linguagens dos exemplos anteriores com os comandos: ls 110* ; ls *0 ; ls *10101*

Autômatos Finitos Determinísticos

As linguagens reconhecidas por AFDs são chamadas regulares, e se você pensou no que eu penso que pensou, então está certo! As strings que fazem parte dessas linguagens regulares são aquelas reconhecidas pelas expressões regulares. Na verdade toda expressão regular tem um AFD equivalente e vice-versa.

Vamos a coisas mais estruturais. Um AFD é composto de

  • estados: sua memória;
  • alfabeto: caracteres usados para formar as entradas a serem testadas pelo autômato;
  • transições: o coração do autômato, diz para qual estado deve ir baseado no símbolo (ou caractere) lido na entrada, e no estado atual (é aqui que entra a função de memória dos estados);
  • estado inicial: onde deve começar a brincadeira;
  • estados finais: se o processamento terminar num estado de final, a string de entrada é considerada válida.

Em símbolos costuma ser assim (na mesma ordem da lista anterior):

M = (Q, Σ, δ, s, F)

Implementação em Python

Tudo muito legal, mas bom mesmo é quando tem código pra nos poupar do trabalho macacal de ficar rodando o AFD na mão, e melhor ainda se o código for em Python. :D

Essa implementação recebe uma 4-upla representando o autômato, mais a string a ser avaliada, retornando True ou False para indicar se a string faz parte da linguagem descrita pelo AFD, ou retorna None, para indicar parâmetros inválidos.

(
ALPHABET,
TRANSITION_FUNCTION,
START_STATE,
FINAL_STATES
) = range(4)

Como você deve ter reparado, o implementação em python recebe uma 4-upla, em lugar da 5-upla descrita anteriormente. O motivo é porque a lista de estados já está embutida na hash table que descreve a função de transição.

def process_string(machine, string):
    if not validate_machine(machine) or
       not validate_string(machine[ALPHABET], string):
        return None    # Processamento do automato.
    state = machine[START_STATE]
    for char in string:
        state = machine[TRANSITION_FUNCTION][state][char]

return (state in machine[FINAL_STATES])

As funções validate_* apenas testam a validade dos parâmetro, a implementação pode ser vista no código fonte (lá embaixo).

Exemplo

O AFD usado como exemplo reconhece a linguagem, sobre o alfabeto {0, 1}, composta de todas as strings que começam com 0, mais a string vazia. Sua representação em forma de grafo é a seguinte (hmm, parece um sapo de óculos):

AFD

Na formalidade, esse autômato M é descrito assim:

M = (Q, Σ, δ, s, F)

  • Q = {q1, q2}
  • Σ = {0, 1}
  • δ(q1, 0) = q1
    δ(q1, 1) = q2
    δ(q2, 0) = q1
    δ(q2, 1) = q2
  • s = q1
  • F = {q1}

Versão pythonizada do autômato:

  • Q: não é usado pelos motivos descritos acima
  • Σ: alphabet = set(['0', '1'])
  • δ: trans_func = {'q1' : {'0' : 'q1', '1' : 'q2'}, 'q2' : {'0' : 'q1', '1' : 'q2'}}
  • s: start_state = 'q1'
  • F: final_states = set(['q1'])

Chamo atenção para a forma de implementação da função de transição, usando dicionários. Dessa forma o equivalente pythonico à forma δ(q1, 0) é trans_func['q1']['0'].

Agora o código para testar algumas strings nesse AFD:

if __name__ == '__main__':
    alphabet = set(['0', '1'])
    trans_func = {'q1' : {'0' : 'q1', '1' : 'q2'},
                  'q2' : {'0' : 'q1', '1' : 'q2'}}
    start_state = 'q1'
    final_states = set(['q1'])
    machine = (alphabet, trans_func, start_state, final_states)
    strings = ['000011111000101010101000', '000011',
               '1', '10', 'a01', '']

for string in strings:
        result = process_string(machine, string)
        if result != None:
            print '%s = %s' % (string, result)

Código-fonte: automato.py

Agora você pode programar seus autômatos e testá-los mais rapidamente, além de gastar menos papel no processo, porque esse mundo está se acabando!

Onde Está Minha Mente

Numa das intermináveis discussões sobre o que existe e o que não existe no universo, Luciano, um auto-reputado ateu ortodoxo, e eu discutíamos sobrevivência da mente após a morte do corpo.

No primeiro ponto de vista a mente é uma função do corpo e morre com ele. Sendo uma função do corpo está sob todas as leis físicas do universo e sendo assim, se tivermos dados sobre o estado inicial do cérebro e conhecermos todas as regras, podemos calcular o pensamento que vai estar passando pela cabeça que contém o tal cérebro. Com mais dados e mais regras podemos fazer isso com qualquer cérebro, com sociedades inteiras, civilizações. Enfim, isso significa que sua opinião sobre este post e o próprio post são totalmente previsíveis, então nem se dê ao trabalho de escrevê-la… se bem que eu me dei o trabalho de escrever esse post, então não tenho moral pra falar nada.

No ponto de vista número dois a mente pode existir sem o corpo. Nesse caso uma coisa externa a um sistema físico dá ordens à esse sistema. A mente pensa algo, comandos são enviados ao corpo via sistema nervoso e temos algo que poderia ser considerado telecinese.

Onde está a mente?

O Rapaz Sem Cérebro

O pediatra e pesquisador John Lorber, da Universidade de Shefield, ao submeter um rapaz à tomografia computadorizada descobriu que ele tinha 1 milímetro de tecido cerebral pesando 50 a 150 gramas, em lugar dos 4,5 centímetros e 1,5 kg habituais. Era um caso de hidrocefalia – e o que faltava de seu cérebro estava preenchido com líquido cefalorraquidiano, que normalmente funciona como um “amortecedor”. A cabeça dele era um aquário de pensamentos.

E agora que você já começou a pensar sobre a capacidade intelectual do sujeito, saiba que ele tem um QI de 126, se graduou com honras em matemática, e possui uma vida social regular.

Esse tipo de fato complica ainda mais a pergunta “onde está a mente?”, mas se me perguntare vou preferir ser uma mente telecinética do que um marionete de um universo mecanicista sem propósito. E pra acabar com música, fecho com Pixies (na versão do Placebo pro filme Clube da Luta):

“With your feet in the air and your head on the ground
Try this trick and spin it, yeah
Your head will collapse
But there’s nothing in it
And you’ll ask yourself

Where is my mind
Where is my mind
Where is my mind”

Refs:

Lógica de Predicados com Python

Ultimamente tenho me divertido revendo algumas coisas de lógica e no momento estou em predicados e quantificadores. Resolvi testar esses conceitos (de forma bem simples) usando Python, assim vou compartilhar minha idéia de diversão com o mundo.

Considere a frase “Marcelo dorme 4 horas por noite”, “Marcelo” é o sujeito e “dorme 4 horas por noite” é o predicado, a lógica de predicados expressa o predicado da afirmação como uma função proposicional onde uma variável representa o sujeito. Estabelecemos que P(x) significa “x dorme 4 horas por noite”, e podemos substituir x por qualquer sujeito, bem não qualquer sujeito e sim algum que esteja no universo de discurso, que nesse caso poderia ser “todos os alunos de computação”. A função P(x) pode ser verdadeira ou falsa, dependendo da qualidade de vida do aluno de computação que substituir x na função.

A outra parte são os quantificadores, que são o universal e o existencial. Usando a função P(x) e o universo de discurso declarados acima, com o quantificador universal posso afirmar que todos os alunos de computação dormem 4 horas por noite”, ou usar o existencial e afirmar que existe pelo menos um aluno de computação que dorme 4 horas por noite”. Para ser verdadeira a proposição quantificada universalmente precisa ser verdade para todos os casos do universo de discurso, já para a proposição quantificada existencialmente, basta que exista um caso verdadeiro para tornar verdadeira a proposição. Pelo menos essa semana posso afirmar que a segunda proposição é verdadeira, infelizmente. :-\

Agora vamos à programação. Em termos algorítmicos a verificação das proposições quantificadas é feita com um loop sobre os elementos do universo de discurso, se a proposição testada for quantificada universalmente o loop pára quando encontrar um resultado falso, que invalida a proposição, se for quantificada existencialmente, ele pára ao encontrar um resultado verdadeiro, que valida a proposição.

Vou usar um exemplo matemático pra facilitar. Considere a função P(x) significando

px

Em Python fica assim:

def P(x):
... return x**2 - 4*x <= 0

Vamos considerar o universo de discurso

xez4×5.png

Agora afirmo que

ax

que é lida como “para qualquer valor de x (dentro do universo de discurso) P(x) é verdadeira”. Ora, P(x) é falsa para x=-1, o que torna falsa a proposição de que P(x) é verdadeira para qualquer valor de x. Expresso logicamente para o universo de discurso declarado acima fica:

ands.png

A avaliação de “para todo” em Python:

def avaliaParaTodo(univ):
... res = True
... for x in univ:
...... res = res and P(x)
...... if not res:
......... return False
... return res

Daí testamos para o universo de discurso (usando range)

>>> avaliaParaTodo(range(-4,5))
False

Vejamos agora o existencial

ex

que é lida como “existe ao menos um valor de x para o qual P(x) é verdadeira”. Com apenas um caso verdadeiro, como x=2, provamos a veracidade da expressão. Também pode ser expresso como:

ors.png

Em Python:

def avaliaExiste(univ):
... res = False
... for x in univ:
...... res = res or P(x)
...... if res:
......... return True
... return res

Avaliando:

>>> avaliaExiste(range(-4,5))
True

Vamos mudar o universo de discurso um pouco, passando a usar o números naturais em lugar dos inteiros:

xen1.png

Agora o teste de ambos os casos, universal e existencial, resulta em verdade:

>>> avaliaParaTodo(range(0,5))
True

>>> avaliaExiste(range(0,5))
True

A coisa pode ficar mais elaborada com funções proposicionais com mais de um argumento, permitindo quantificações como “para todo x existe um y”, que algorítmicamente seria expressa com dois loops aninhados.

Depois disso tudo você pode querer mandar para sua namorada uma representação em lógica de predicados de “x ama y” ou algo assim. As mulheres adoram.

Referências:

Ah, e as fórmulas foram produzidas no OpenOffice.org Math