Máquinas de Turing

Autômatos, Linguagens e Computação

Pontifícia Universidade Católica de Campinas

Prof. Dr. Denis M. L. Martins

Objetivos de Aprendizagem

  • Apresentar o conceito e funcionamento de Máquinas de Turing (MT).
  • Explorar variações como Máquinas de Turing com fitas múltiplas e não-determinísticas.
  • Discutir a relação entre MTs e a definição de problemas decidíveis e indecidíveis.

Alan Turing

  • Nasceu em 23 de junho de 1912 em Londres, Inglaterra
  • Aos 24 anos, em 1936, propõe as "A-Machines": Máquina de Turing, um modelo abstrato de computação com o poder dos computadores modernos
    • Formalizou o conceito de algoritmo e investigar quais problemas poderiam ser resolvidos computacionalmente. Limites da Computação.
    • Fundamentou os conceitos de Computabilidade e Complexidade.
    • Trabalho seminal: "On computable numbers, with an application to the Entscheidungsproblem"
  • Segunda Guerra Mundial: Trabalhou em Bletchley Park, liderando a equipe que decifrou o código Enigma

Máquinas de Turing

Anatomia - Componentes Básicos

  • Fita de entrada infinita (para a direita)
  • Cabeça/Cursor de leitura/escrita
    • Pode se mover para esquerda ou para direita
  • Estados e função de transição
  • Dois estados especiais com efeito imediato
    • : a MT para e aceita a cadeia de entrada w
    • : a MT para e rejeita a cadeia de entrada w
  • Nota: semelhante a um AF, mas com memória ilimitada e acesso irrestrito.


Modelo Físico de uma MT.
Note que a natureza nos impede de ter uma fita infinita. Veja mais em: https://aturingmachine.com

Definição de Máquina de Turing

  • Definição (Máquina de Turing): uma MT é uma 7-upla , onde:
    • é o conjunto de estados
    • é o alfabeto de entrada
    • é o alfabeto da fita ()
    • é a função de transição no formato
      • é o sentido do movimento do cursor e assume para Esquerda ou Direita
    • é o estado inicial
    • é o estado de aceitação
    • é o estado de rejeição

Funcionamento de uma Máquina de Turing

  • O Funcionamento geral de uma MT é dado como se segue:
    • A cadeia é escrita na fita
    • A MT começa com o cursor na posição mais à esquerda
    • A computação procede de acordo com a função de transição :
      • Quando em um estado , e lê um símbolo 'a':
        • muda para o estado
        • Escreve 'b' na fita no lugar de 'a'; e
        • Move o cursor para a esquerda ou para direita.
    • A computação continua até que alcance ou e a máquina para.
  • Pergunta: O que acontece se o cursor estiver mais à esquerda e a transição tenta mover o cursor à esquerda com ?
  • Resposta: Nenhum movimento é feito.

Exemplo

Funcionamento de uma MT que reconhece .

O diagrama de estados e transições está ilustrado ao lado.

Vamos verificar a cadeia de exemplo passo a passo.

Exercício: Descreva o diagrama de estados de uma MT que reconhece

Configuração de uma Máquina de Turing

Descrição instantânea

  • Uma configuração de uma MT descreve:
    • Seu estado atual;
    • O conteúdo da fita; e
    • A posição atual do cursor de leitura/escrita.
  • Representação: .
  • Dizemos que uma configuração origina se a MT puder ir de a em um único passo, denotado .
  • Exemplos: , ,

Definição de aceite

Dizemos que uma MT aceita uma cadeia se existe uma sequência de configurações:

onde:

  • (1) é a configuração inicial
  • (2) Cada origina
  • (3) é uma configuração de aceitação

A MT rejeita se em (3) o estado de configuração é de rejeição.

Variantes de uma MT

  • Expandem o modelo padrão para explorar diferentes aspectos de computação.
  • MT Multifitas: possuem várias fitas para leitura e escrita simultânea, aumentando a eficiência.
  • MT Não-Determinísticas: permitem múltiplos caminhos de execução ao mesmo tempo.
  • Essas variações ajudam a entender questões como eficiência, paralelismo e universalidade no processamento computacional.
  • Robustez: Reconhecem a mesma classe de linguagens. Ou seja, possuem o mesmo poder computacional.

MT Multifitas

  • Utiliza várias fitas, cada uma com seu próprio cursor de leitura/escrita.
  • Isso permite que a máquina leia e escreva em múltiplas posições simultaneamente, tornando-a mais eficiente em certos problemas.
  • A função de transição é ajustada para lidar com o estado atual e os símbolos lidos em todas as fitas, determinando o próximo estado, os símbolos a serem escritos e os movimentos das cabeças de leitura/escrita em cada fita.
  • Equivalência ao modelo padrão: qualquer multifita pode ser simulada por uma MT de fita única.
  • Ideia de prova: Concatenar as k fitas na fita S com o delimitador . A posição de cada cursor é representada pelo símbolo . Simular a função de transição:

Pergunta

  • A definição que vimos é de uma MT determinística. Qual modificação precisa ser feita para torná-la Não-Determinística?
    • Alterar
    • Alterar
    • Alterar
  • Resposta: B

MT Não-Determinística

  • Modificamos a função de transição:
  • Assim como nos Autômatos Finitos, o não-determinismo não acrescenta poder computacional às MTs.

center

MT Não-Determinística

  • Equivalência: Uma MT Não-Determinística é equivalente a uma MT padrão
  • Uma MT Não-Determinística aceita uma cadeia se pelo menos um ramo leva ao estado de aceitação.
  • Ideia de Prova: Simular uma MT Não-Determinística com uma MT de 3 fitas. Busca em largura na árvore de computação.

center

Linguagem Reconhecida por uma Máquina de Turing

  • Todas as cadeias aceitas por uma MT formam a linguagem de , ou seja, a linguagem reconhecida por , denotada .
  • Note que , então pode:
    • Rejeitar : parar no estado de rejeição; ou
    • Nunca parar: entrar em loop infinito
  • O conjunto de linguagens que podemos aceitar usando uma MT é chamado linguagens recursivamente enumeráveis.
  • Linguagens recursivas são aquelas que podem ser decididas por uma MT que sempre para.

Tese de Church-Turing

  • A Tese Church-Turing propõe que qualquer cálculo ou problema que possa ser resolvido por um algoritmo pode ser realizado por uma Máquina de Turing.
  • Embora não seja formalmente provada, é amplamente aceita como a definição prática de computabilidade.

Dica Cultural

Mais uma Dica

center
YouTube: https://www.youtube.com/watch?v=YzXoFldEux4.
Baseado no artigo https://arxiv.org/pdf/1904.09828.
Código Python: https://github.com/Cerno-b/mtg-turing-machine

Mais outra Dica

center
YouTube: https://youtu.be/soJ3FPvs7QI?si=rLK59BfBtNpnLUVZ.
Leia mais em https://teachinglondoncomputing.org/turingmachine/