Mind map

Máquina de Turing

Ricardo Graciano Portuguese

Map content

Máquina de Turing

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)
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
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