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.

• Download 6936.turing.zip
• Enviar nova versão

Esconder código-fonte

#!/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 + "&#8630;"

      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

Gerador de cartão de crédito com Tkinter

Cálculo do dia da Páscoa

Algoritmo de Dijkstra em Python com visualização em PyGraphviz

Brincando com conjuntos

Interface para qemu