Máquina de Turing em Python 3
Publicado por Luis Pereira (última atualização em 15/01/2019)
[ Hits: 6.729 ]
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
Compartilhe suas configurações gconf
Jogo de adivinhar o número aleatório
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Meu Fork do Plugin de Integração do CVS para o KDevelop
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
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Cups: Mapear/listar todas as impressoras de outro Servidor CUPS de forma rápida e fácil
Criando uma VPC na AWS via CLI
Tem como instalar o gerenciador AMD Adrenalin no Ubuntu 24.04? (15)
Tenho dois Link's ( IP VÁLIDOS ), estou tentando fazer o failover... (0)
Pendrive não formata de jeito nenhum (4)