Máquina de Turing em Python 3

luishenriquem

Este script é uma simples implementação da máquina de Turing, conforme descrito em DIVERIO e MENEZES, 2009. Para utilizá-lo basta baixar o arquivo zip, e descompactar os arquivos em um diretório. Em seguida, executar o script e fornecer as informações solicitadas (caminho do arquivo contendo o programa, estado inicial e estados finais e a entrada do programa). Algumas explanações: - "*": símbolo inicial da fita; - "_": símbolo de fita em branco; - "<" e ">": instrução para a máquina mover a posição de leitura para a esquerda e direita, respectivamente; - O programa "potencia.txt" recebe como entrada um número natural em notação unária (vários "uns" representando os números, por exemplo, 3 em unário é 111) e encerra a execução com o quadrado desse número escrito na fita. - As linhas do programa desta implementação da máquina de Turing, instruem a "máquina" sobre o que fazer: se, por exmplo, o atual estado for "q2", a leitura da fita for "A" a "máquina" deve ir para o estado "q3" escrever "B" na fita e mover para a direita. A notação no programa ficaria, "q2 A q3 B >"; - Para mais detalhes sobre o funcionamento da máquina de Turing, consultar a referência. Referência: DIVERIO, Tiarajú A.; MENEZES, Paulo B. Teoria da Computação--UFRGS: Máquinas Universais e Computabilidade. Bookman Editora, 2009.

Por: Luis Pereira