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>