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.

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

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.

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.

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:

• turingmachine.py

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.

<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).

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. 😀

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):

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:

• Where Is Consciousness? I’ve Lost It!
• Is your brain really necessary?

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

Em Python fica assim:

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

Vamos considerar o universo de discurso

Agora afirmo que

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:

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

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:

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:

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:

• Predicate Logic
  
• Lógica de Primeira Ordem
  
• ROSEN, Kenneth H. Discrete Mathematics and Its Applications

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