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.

LogicParser 0.4

Mais um release do LogicParser, agora a aba “Graph (Image)” é atualizada com imagem representando a árvore parseada da expressão lógica.

LogicParser 0.4

Duas funções muito boas da GLib me ajudaram:

  • g_file_set_contents: escreve todo conteúdo de uma string para um arquivo. Simples e rápida.
  • g_spawn_sync: dispara um processo de forma síncrona, para chamar o dot, do GraphViz.

Juntanto com outras facilidades da GLib, programar em C fica fácil demais. :P

Outra coisa muito útil era o Google Code Search, a referência da GLib é muito boa, mas às vezes você quer ver o código sendo usado, e o code search ajudou bastante. Por exemplo, a especificação do g_spawn_sync tem muitos parâmetros, assustadores numa primeira olhada. “Como devo setar esses parâmetros?” Como todo mundo! No código do eog que achei nessa busca: lang:c g_spawn_sync

Sobre o futuro, o código precisa de mais “polish” e certamente preciso aprender CMake ou Autotools pra fazer um build system de respeito e não meu seboso Makefile. Por ser um projeto pequeno, pode valer à pena aprender Autotools.

Lembrando:

Update: OMG! Agora o Google Hosting disponibiliza uma wiki! Vejam a minha: http://code.google.com/p/logicparser/wiki/LogicParser

Audiobooks

Se tem uma coisa que acho irritante é me deslocar (também odeio calor e verão, mas isso é só mais um fator cumulativo). Quase todo dia viajo 3 horas (ida e volta e meia hora na fila do ônibus) pra universidade, e às vezes mais 3 horas (ida e volta) pra o Espaço Ciência. Se eu tivesse um laptop podia fazer dos ônibus meu escritório e montar um negócio paralelo, mas não creio que eu fosse andar de ônibus com um laptop. ¬¬

Contudo!!! Há uma luz no fim do túnel! Ou melhor, um som: audiolivros! Já ouvi O Hobbit, O Senhor dos Anéis, e agora filosofia Grega, de Tales até Aristóteles.

Continuo não gostando de viajar de ônibus, mas agora sei que toda filosofia ocidental pode ser considerada comentários à respeito de Platão e Aristóteles, que os sofistas viraram advogados e que Sócrates continua o debate, ou melhor, o diálogo, com os neurocientistas pré-socraticos. Enfim, não há nada de novo sob o sol, que continua impiedoso no verão. ¬¬

Nota: Gostei particularmente desse grafo, feito com o GraphViz, das relações de influência entre os filósofos pré-socráticos.

LogicParser 0.2

Segundo release do LogicParser. Está sendo bem divertido voltar a programar em C, ainda mais com a GLib facilitando as coisas. No começo é estranho usar g_print no lugar de printf, e outras coisas, mas quando penso que boa parte da portabilidade estará garantida quando for compilar esse treco em Win32… :)

Neste release adicionei um componente para gerar grafos no no formato da linguagem DOT, processados pela ferramenta homônima do pacote GraphViz.

Aqui está uma expressão na sintaxe compreendida pelo LogicParser:

p1->(f | (!p3))

O grafo gerado:

digraph ParsedTree {
if_then_0 [label=if_then];
if_then_0 -> P1_1;
if_then_0 -> or_2;
P1_1 [label=P1];
or_2 [label=or];
or_2 -> False_3;
or_2 -> not_4;
False_3 [label=False];
not_4 [label=not];
not_4 -> P3_5;
P3_5 [label=P3];
}

A linha de invocação do dot, e a figura gerada:
dot -Tpng grafo.dot -o grafo.png

p1->(f | (!p3))

Além disso tudo está documentado na sintaxe do Doxygen.

Update: ah! O comando mágico para criar um tag no subversion:
svn copy https://logicparser.googlecode.com/svn/trunk \
https://logicparser.googlecode.com/svn/tags/release-0.2 \
-m "Release 0.2 of the 'LogicParser' project."