Maquina de Turing

Máquina de Turing

Teoria da Computação

Máquina de Turing

Wellington Aparecido Della Mura

Universidade Estadual do Norte do Paraná

Centro de Ciências Tecnológicas

[email protected]

Wellington Aparecido Della Mura Teoria da Computação

Máquina de Turing

IntroduçãoNoção intuitiva e formalModelos equivalentes à Máquina de TuringHipótese de Church

Aulas anteriores

Linguagens Livres de Contexto

Autômatos com Pilha

Poder de reconhecimento do AP


Máquina de Turing


Aula de hoje

Objetivo: Introduzir a Máquina de TuringHistórico

Noção intuitiva e formal

Modelos equivalentes

Hipótese de Church

Motivação

É a formalização mais utilizada de algoritmo;

Seu funcionamento é base para a computação atual;

Serve para o entendimento da noção de computabilidade.

Existem mais problemas não solucionáveis do quesolucionáveis.


Máquina de Turing


Contextualização

David Hilbert (1928) propôs o Problema de DecisãoExiste um procedimento mecânico capaz de decidir, emtempo �nito, se uma proposição é válida ou não?

Kurt Gödel (1931) propôs o Teorema da Não CompletudeProvando a existência de proposições indecidíveis

Máquinas Universais:Máquina de TuringMáquinas com pilhasMáquina de PostMáquina NormaFunções Recursivas de KleeneCálculo Lambda


Máquina de Turing


Histórico

A Máquina de Turing foi proposta porAlan Turing em 1936.

O primeiro formalismo com a noção dealgoritmos e do que seria computável.

Algoritmo

Sequência �nita de instruções discretas realizadasmecanicamente em um tempo �nito.

Hipótese de Church: qualquer função computável podeser processada por uma Máquina de Turing.

Noção de algoritmo não é matematicamente precisa.


Máquina de Turing


Aplicabilidade da Máquina de Turing

Processamento de FunçõesConceito de funções computáveis e suas propriedades

Reconhecimento de LinguagensFormalismo reconhecedor de linguagens RecursivamenteEnumeráveis

Solucionabilidade de ProblemasDe�nir se os problemas são solucionáveis, nãosolucionáveis, parcialmente solucionáveis ou insolúveis.


Máquina de Turing


Noção Intuitiva

Mecanismo simples que formaliza a ideia de uma pessoaque realiza cálculos.Uma pessoa, equipada com uma caneta e um apagador,realiza cálculos em uma folha de papel, organizada emquadrados.Os quadrados contém apenas dados iniciais do problema.A pessoa realiza operações simples:

1 Ler um símbolo do quadrado;2 Alterar um símbolo do quadrado;3 Mover os olhos para outro quadrado (esquerda/direita)

O comportamento, a cada momento, é determinado peloestado presente e o símbolo no quadrado atual.Termina quando chega em uma resposta satisfatória.


Máquina de Turing


Noção como Máquina

A noção de uma pessoa calculando pode ser vista como umamáquina de estados �nitos formada por:

Fita: que serve de dispositivo de entrada, de saída ememória de trabalho.

Unidade de Controle: representa o estado corrente damáquina e possui uma unidade de leitura e gravação.Pode de movimentar para a esquerda ou para a direita.

Função de transição (programa): De�ne o próximo estadoda máquina, comanda as leituras, gravações e a direçãode movimento da leitura.


Máquina de Turing


Representação Grá�ca da Máquina

A �ta é �nita à esquerda e in�nita à direitaSímbolo na �ta pode pertencer ao alfabeto de entrada, aoalfabeto auxiliar, ser branco ou marcar o início de �ta.Inicialmente a única informação que existe na �ta é seumarcador de início seguido da entrada.


Máquina de Turing


Representação Formal

M = 〈Σ, Q, δ, q0, F, V, β,Θ〉

Σ: alfabeto de símbolos de entrada;

Q: conjunto �nito de estados possíveis da máquina;

δ: é a função de transição (programa) tal que:δ : Q×(Σ∪V ∪{β,Θ})→ Q×(Σ∪V ∪{β,Θ})×{E,D}q0: estado inicial tal que q0 ∈ Q;F : conjunto de estados �nais tal que F ⊆ Q;

V : é um alfabeto auxiliar (pode ser vazio);

β: é o símbolo especial branco;

Θ: é o marcador de início de �ta.


Máquina de Turing


Função de Transição

A Função de Transição:

Considera o estado corrente e o símbolo lido na �ta.

Determina um novo estado, o símbolo a ser gravado na�ta e o sentido do movimento da cabeça de leitura.

A transição δ(p, x) = (q, y,m) é representada por:


Máquina de Turing


Computação da Máquina de Turing

O processamento para uma entrada w consiste em:

Aplicação sucessiva da função programa a partir do estadoinicial q0 e da cabeça posicionada mais à esquerda da �ta.

A execução da função programa ocorre até que se atinjauma condição de parada.

O processamento pode:

parar; ou

�car processando inde�nidamente(ciclo ou loop in�nito).


Máquina de Turing


Condição de Parada

A parada do processamento de uma Máquina de Turing parauma entrada w pode acontecer de duas maneiras:

Aceita a entrada w.Quando atinge o estado �nal e a máquina para;

Rejeita a entrada w. Quando:A função programa é inde�nida; ouA função programa de�ne um movimento à esquerda noinício da �ta.


Máquina de Turing


Linguagens Aceita, Rejeitada e Loop

Seja M = 〈Σ, Q, δ, q0, F, V, β,Θ〉 uma Máquina de Turing,então:

A linguagem aceita (reconhecida) por M é denotada porACEITA(M) ou L(M).A linguagem rejeitada por M é denotada porREJEITA(M).A linguagem loop de M , denotada por LOOP (M).


Máquina de Turing


Exemplo: Problema do Duplo Balanceamento

Seja uma MT que aceite a linguagem L = {anbn | n ≥ 0}


Máquina de Turing


Exemplo: Função de Transição

δ Θ a b A B βq0 (q0,Θ, D) (q1, A,D) (q3, B,D) (q4, β,D)q1 (q1, a,D) (q2, B, E) (q1, B,D)q2 (q2, a, E) (q0, A,D) (q2, B, E)q3 (q3, B,D) (q4, β,D)q4

Dada a entrada w = aabb, os passos de processamento são:


Máquina de Turing


Máquina de Turing x Algoritmo

A Máquina de Turing é aceita como uma formalização doconceito de algoritmo.

É usual considerar como conceito de algoritmo:Máquina de Turing que sempre para a qualquer entrada.

Uma máquina que eventualmente �ca em loop in�nito:Não seria considerada um algoritmo.


Máquina de Turing


Modelos Equivalentes à Máquina de Turing

A Máquina de Turing é considerada o mais geral dispositivo decomputação

Todos os demais modelos e máquinas propostosNormaPostAutômato com Pilha

As diversas modi�cações da Máquina de Turing

Possuem, no máximo, o mesmo poder computacional daMáquina de Turing.


Máquina de Turing


Autômato com Múltiplas Pilhas

O autômato com pilha é um formalismo reconhecedor daslinguagens livres de contexto.

Um autômato com duas pilhas possui o mesmo poder deuma MT;

Um maior número de pilhas não aumenta a capacidadecomputacional;

A estrutura de �ta é mais expressiva do que a de pilha.


Máquina de Turing


MT com Fita In�nita à Esquerda e à Direita

Uma MT com �ta in�nita dos dois lados não aumenta o podercomputacional.

Pode ser facilmente simulada por uma �ta tradicional:Células pares: parte direita da �ta; eCélulas ímpares: parte esquerda da �ta.


Máquina de Turing


Outras modi�cações da Máquina de Turing

Máquina de Turing Não-Derminística

Máquina de Turing com Múltiplas Fitas

Máquina de Turing Multidimensional

Máquina de Turing com Múltiplas Cabeças

Modi�cações combinadas

A combinação de algumas ou todas as modi�cações nãoaumenta o poder computacional da Máquina de Turing


Máquina de Turing


Hipótese de Church

Objetivo do modelo abstrato de computação Máquina deTuring:

Explorar os limites da capacidade de expressar soluções deproblemas;

Uma proposta de de�nição formal da noção intuitiva dealgoritmo;

Existiram diversos outros trabalhos equivalentes ao de Turing,como:

1 Máquina de Post (Post - 1936)2 Funções Recursivas (Kleene - 1936)


Máquina de Turing


Hipótese de Church (cont.)

Forte reforço da Hipótese de (Turing-) Church

"A capacidade de computação representada pela Máquina de

Turing é o limite máximo que pode ser atingido por qualquer

dispositivo de computação".

Remete ao conceito de Máquinas Universais

Hipótese de Church não é demonstrávelUm algoritmo ou função computável não ématematicamente preciso.Não há como de�nir o conjunto de todas as máquinaspossíveis.

Reconhecida para toda a teoria da computação clássica.Wellington Aparecido Della Mura Teoria da Computação

Máquina de Turing


Revisão

1 De�nição de algoritmo2 Noção intuitiva da MT3 Modelo formal da MT4 Condições de parada e loop

5 Modelos equivalentes à MT6 Hipótese de Church


Máquina de Turing


Exercícios

Lista de Exercícios

Ferramenta para simulação da MT: JFLAP(http://www.j�ap.org/)


Máquina de Turing


Próxima Aula

Máquina de Turing como Reconhecedor de Linguagem

Máquina de Turing como Processador de Funções


Máquina de Turing


Bibliogra�a

MENEZES, P. B. Linguagens Formais e autômatos.v.3, 6a ed. Porto Alegre: Bookman, 2011. (cap.8)

DIVERIO, T. A.; MENEZES, P. B. Teoria daComputação: máquinas universais e computabilidade.v. 5, 3a ed. Porto Alegre: Bookman, 2011.(cap.5)

LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos eTeoria da Computação. v. 2. Porto Alegre: Bookman,2000.(cap.4)

HOPCROFT J. E.; MOTWANI H. ; ULLMAN J. D.Introduction to Automata Theory, Languages, andComputation. v.2. Addison-Wesley, 2001.(cap.8)


Education

Maquina de Turing