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!