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 CPF em Python

Passgen

Verificar se um número é primo

Sugestão aleatória de filmes e séries para assistir por streaming

Desquebra-Cabeça dos Palitos