Máquina de Turing

Máquina de Turing

1. Constituição

   • Fita
     • Utilizada como compartimento de entrada, de saída e como dispositivo de memória de trabalho
   • Unidade de Controle
     • Mostra o estado em que a máquina se encontra
   • Programa ou Função de Transição
     • Função que define e comanda as leituras, as gravações e em qual sentido se movimenta a unidade de controle (cabeça da máquina)

2. Software para construção

   • Visual Turing 2.0
     • Benefícios
       • é possível a definição de símbolos
       • relacionamentos e instruções entre os símbolos
       • permite que seja definida uma fita, de tamanho infinito
         • onde cada posição contém um símbolo a ser verificado durante a execução da máquina de Turing

3. Problema destacado

   • Através de uma máquina de Turing, fazer a comparação de duas listas com o objetivo de manter as palavras escritas na primeira lista que se encontram presentes na segunda lista
     • Exemplo
       • Entrada
         • #z#aa#bbbb#bba#z#bba#aab#bbbb#b#aaa#bb#z#
       • Saída
         • hg#z####bbbb#bba#z#
           • hg representa o número (binário) de palavras na intersecção. h = 1 g = 0
   • Implementação da Solução
     • Algoritmo definido pra solução
     • Máquina implementada
       • Sub-máquinas utilizadas na implementação
         • inicial
           • que inicializa as listas marcando a primeira palavra de cada uma das listas
         • prox_let
           • que posiciona a cabeça da fita na próxima letra da palavra que está sendo analisada na segunda lista
         • prox_pal
           • que pula para a próxima palavra da segunda lista
         • volta_pal
           • que retorna para a letra a ser verificada da palavra da primeira lista que está sendo analisada
         • reinicia_pal
           • que retorna para a letra a ser verificada da palavra da primeira lista que está sendo analisada
         • aceita_pal
           • que marca como aceita a palavra da primeira lista encontrada na segunda lista e marca a próxima palavra da primeira lista
         • recusa_pal
           • que marca como aceita a palavra da primeira lista encontrada na segunda lista e marca a próxima palavra da primeira lista
         • final
           • que apaga a segunda lista após todas as palavras da primeira lista terem sido procuradas
         • contabil
           • que conta quantas palavras da primeira lista foram aceitas, isto é, a cardinalidade da intersecção das listas
             • Sub-máquina mais_um

Bilder und Dateien der Mindmap