Máquina de Turing em Python 3
Publicado por Luis Pereira (última atualização em 15/01/2019)
[ Hits: 6.661 ]
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
Just Do It - XML Generic Editor
Avaliador de Expressões Simples
Mudar wallpaper por um aleatorio
Script de Inventário em Python
Gerador de números para Mega-Sena
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Flatpak: remover runtimes não usados e pacotes
Mudar o gerenciador de login (GDM para SDDM e vice-versa) - parte 2
Inkscape Atualização 1.4 [RESOLVIDO] (8)
samba4 - 4.21 utilizar phpldapadmin [RESOLVIDO] (5)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta