Máquina de Turing em Python 3
Publicado por Luis Pereira (última atualização em 15/01/2019)
[ Hits: 6.804 ]
Homepage:
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.
#!/usr/bin/python3 # -*- coding: utf-8 -*- # turing.py Uma implementação da máquina de Turing para fins didáticos. # # Copyright (C) 2019 Luis Pereira # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 3 of the License, or # (at your option) any later version. # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program. If not, see <https://www.gnu.org/licenses/>. import sys import time class Turing: def __init__(self): pass def setTape(self, entry): tape = "*"+entry+"_____________________________________________________________________________________________________________" self.tape = list(tape) def initalState(self, initial): self.initial = initial def finalStates(self, finals): self.finals = finals.split(" ") def readProgram(self, _file): try: fprog = open(_file, "r") line = fprog.readline() self.transtions = {}; while line : transtion = line.replace("\n", "").split(" "); self.transtions[(transtion[0], transtion[1])] = (transtion[2], transtion[3], transtion[4]) line = fprog.readline() fprog.close() except: print("Erro de E/S") exit() def printTape(self, pos): arrow = "" output = "" for x in range(pos): arrow = arrow + " " arrow = arrow + "↶" for char in self.tape: output = output + char print(arrow) print(output+"\n") def run(self): pos = 0 currState = self.initial keys = list(self.transtions.keys()) interaction = 1 while True: if keys.count((currState, self.tape[pos])) == 1 : print("Estado atual => " + currState) print("Simbolo lido => " + self.tape[pos]) action = self.transtions[(currState, self.tape[pos])] print("Proximo estado => " + action[0]) print("Simbolo escrito => " + action[1]) print("Movimento => " + action[2]) self.printTape(pos) print("Interações: %d" % interaction) interaction = interaction + 1 # Permite que o usuário avnace nos ciclos de execução, pressionando ENTER input("") #time.sleep(0.7) currState = action[0] self.tape[pos] = action[1] if(action[2] == "<"): pos = pos - 1 else: pos = pos + 1 else: break if self.finals.count(currState) == 1 : print("Palavra aceita") else: print("Palavra rejeitada") def test(self): print(self.finals) ############################################################################### tur = Turing() tur.readProgram(input("Entre com o arquivo do programa: ")) tur.initalState(input("Informe o estado inicial: ")) tur.finalStates(input("Informe os estados finais: ")) tur.setTape(input("Entrada: ")) tur.run() # Fim do arquivo turing.py # Inicio do arquivo potencia.txt q0 * q0 * > q0 B q0 B > q0 _ q3 _ < q0 1 q1 A > q1 _ q2 B < q1 1 q1 1 > q1 B q1 B > q2 1 q2 1 < q2 B q2 B < q2 A q0 A > q3 B q4 _ < q3 * q3 * > q4 B q4 B < q4 A q5 A > q5 B q6 C < q5 _ q12 _ < q6 A q6 1 < q6 C q6 C < q6 * q7 * > q7 1 q8 A > q8 1 q9 A > q8 C q11 C > q9 C q9 C > q9 B q9 B > q9 1 q9 1 > q9 _ q10 1 < q10 C q10 C < q10 B q10 B < q10 1 q10 1 < q10 A q8 A > q11 C q11 C > q11 B q6 C < q11 1 q12 1 < q12 A q12 1 < q12 C q12 1 < q12 * q13 * > # Fim do arquivo potencia.txt
Calcula a idade da pessoa em dias
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Título: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Instalando Brave Browser no Linux Mint 22
vídeo pra quem quer saber como funciona Proteção de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
VMs e Interfaces de Rede desapareceram (12)
Instalação do drive do adaptador wiffi (7)