17_CapIII_descrevendoMT

Prévia do material em texto

CET089 - Teoria da Computação
III - Máquinas de Turing
Departamento de Ciências Exatas e Tecnológicas - DCET
Universidade Estadual de Santa Cruz - UESC
BA
Teoria 1
Revisão
Revisão
Introdução à TC:
Teoria dos autômatos, Teoria da computabilidade e Teoria da
complexidade.
Cap I - LR: AFD, LR, 3 operações sobre LR:
União (∪), concatenação (◦), Estrela (∗).
AFN; AFN ∼= AFD.
ER; ER AFN; AFD AFNG ER.
Aplicações de ER.Lema do bombeamento.
Cap II - LLC: GLC; ambiguidade; FNC; AP; LB.
Cap III - MT: definição formal; LTD (recursivas); LTR (rec. enumeráveis);
MT Multifita; MT não-determinística; MT ND linearmente limitada;
Hierarquia de Chomsky; definição de algoritmo - Tese de Church-Turing;
Objetivo: Cap III - Máquinas de Turing.
Teoria 2
Máquina de Turing
Revisando: tese Church-Turing
Algoritmo: Sequência finita de instruções que corretamente
soluciona todas as instâncias de um problema em tempo finito;
Um problema tem um algoritmo que o resolva se e somente se
existe uma MT que o decide.
Não foi demonstrada, mas é amplamente aceita.
Teoria 3
Máquina de Turing
Padronizar a descrição informal de MT
Qual o nível de detalhe para descrever o funcionamento de MT?
Formal - tupla (Q,Σ, Γ, δ, qinicial, qaceitação, qrejeição).
Informal = alto nível - linguagem natural.
Entrada: cadeia.
Objeto cadeia.
Notação: 〈O〉
Significado: Objeto O representado como cadeia.
Exemplo: L = {〈O〉| O é um número primo }
O = 2 〈O〉 = 10.
O = 3 〈O〉 = 11.
Notação: 〈O1,O2, ...,Ok〉
Significado: Objetos O1,O2, ...,Ok representados como cadeia.
G = (V ,A) 〈G 〉 = (1, 2, 3, 4)((1, 2)(2, 3), (3, 1)(1, 4)).
Funcionamento da MT = segmento indentado de texto dentro
de aspas dupla.
Particionado em estágios.
Primeira linha descreve a entrada da MT.
Teoria 4
Máquina de Turing
Padronizar a descrição informal de MT
Qual o nível de detalhe para descrever o funcionamento de MT?
Formal - tupla (Q,Σ, Γ, δ, qinicial, qaceitação, qrejeição).
Informal = alto nível - linguagem natural.
Entrada: cadeia.
Objeto cadeia.
Notação: 〈O〉
Significado: Objeto O representado como cadeia.
Exemplo: L = {〈O〉| O é um número primo }
O = 2 〈O〉 = 10.
O = 3 〈O〉 = 11.
Notação: 〈O1,O2, ...,Ok〉
Significado: Objetos O1,O2, ...,Ok representados como cadeia.
G = (V ,A) 〈G 〉 = (1, 2, 3, 4)((1, 2)(2, 3), (3, 1)(1, 4)).
Funcionamento da MT = segmento indentado de texto dentro
de aspas dupla.
Particionado em estágios.
Primeira linha descreve a entrada da MT.
Teoria 4
Máquina de Turing
Padronizar a descrição informal de MT
Qual o nível de detalhe para descrever o funcionamento de MT?
Formal - tupla (Q,Σ, Γ, δ, qinicial, qaceitação, qrejeição).
Informal = alto nível - linguagem natural.
Entrada: cadeia.
Objeto cadeia.
Notação: 〈O〉
Significado: Objeto O representado como cadeia.
Exemplo: L = {〈O〉| O é um número primo }
O = 2 〈O〉 = 10.
O = 3 〈O〉 = 11.
Notação: 〈O1,O2, ...,Ok〉
Significado: Objetos O1,O2, ...,Ok representados como cadeia.
G = (V ,A) 〈G 〉 = (1, 2, 3, 4)((1, 2)(2, 3), (3, 1)(1, 4)).
Funcionamento da MT = segmento indentado de texto dentro
de aspas dupla.
Particionado em estágios.
Primeira linha descreve a entrada da MT.
Teoria 4
Máquina de Turing
Padronizar a descrição informal de MT
Qual o nível de detalhe para descrever o funcionamento de MT?
Formal - tupla (Q,Σ, Γ, δ, qinicial, qaceitação, qrejeição).
Informal = alto nível - linguagem natural.
Entrada: cadeia.
Objeto cadeia.
Notação: 〈O〉
Significado: Objeto O representado como cadeia.
Exemplo: L = {〈O〉| O é um número primo }
O = 2 〈O〉 = 10.
O = 3 〈O〉 = 11.
Notação: 〈O1,O2, ...,Ok〉
Significado: Objetos O1,O2, ...,Ok representados como cadeia.
G = (V ,A) 〈G 〉 = (1, 2, 3, 4)((1, 2)(2, 3), (3, 1)(1, 4)).
Funcionamento da MT = segmento indentado de texto dentro
de aspas dupla.
Particionado em estágios.
Primeira linha descreve a entrada da MT.
Teoria 4
Máquina de Turing
Padronizar descrição informal de MT
Exemplo: Seja A a linguagem:
A = {〈N〉| N é um número primo.}
A codificação que usaremos aqui é a seguinte:
N = 2 então 〈N〉 = aa.
N = 3 então 〈N〉 = aaa.
N = 5 então 〈N〉 = aaaaa.
Teoria 5
Máquina de Turing
Padronizar descrição informal de MT
Logo: A = {an| n é um número primo.}
Uma MT que decide A:
M="Sobre a entrada 〈N〉, ou seja an, n primo:
1 Gerar os inteiros k de 2 a n-1;
2 Determinar se k divide n, usando subtrações sucessivas.
3 Se algum k divide n rejeite senão aceite."
Exemplo: n=5
] a a a a a F a a t ...
] X a a a a F a a t ...
] X a a a a F X a t ...
] X X a a a F X a t ...
] X X a a a F X X t ...
] X X a a a F a a t ...
] X X X a a F a a t ...
] X X X a a F X a t ...
Teoria 6
Máquina de Turing
Padronizar descrição informal de MT
Logo: A = {an| n é um número primo.}
Uma MT que decide A:
M="Sobre a entrada 〈N〉, ou seja an, n primo:
1 Gerar os inteiros k de 2 a n-1;
2 Determinar se k divide n, usando subtrações sucessivas.
3 Se algum k divide n rejeite senão aceite."
Exemplo: n=5
] a a a a a F a a t ...
] X a a a a F a a t ...
] X a a a a F X a t ...
] X X a a a F X a t ...
] X X a a a F X X t ...
] X X a a a F a a t ...
] X X X a a F a a t ...
] X X X a a F X a t ...
Teoria 6
Máquina de Turing
Padronizar descrição informal de MT
Logo: A = {an| n é um número primo.}
Uma MT que decide A:
M="Sobre a entrada 〈N〉, ou seja an, n primo:
1 Gerar os inteiros k de 2 a n-1;
2 Determinar se k divide n, usando subtrações sucessivas.
3 Se algum k divide n rejeite senão aceite."
Exemplo: n=5
] a a a a a F a a t ...
] X a a a a F a a t ...
] X a a a a F X a t ...
] X X a a a F X a t ...
] X X a a a F X X t ...
] X X a a a F a a t ...
] X X X a a F a a t ...
] X X X a a F X a t ...
Teoria 6
Máquina de Turing
Padronizar descrição informal de MT
Logo: A = {an| n é um número primo.}
Uma MT que decide A:
M="Sobre a entrada 〈N〉, ou seja an, n primo:
1 Gerar os inteiros k de 2 a n-1;
2 Determinar se k divide n, usando subtrações sucessivas.
3 Se algum k divide n rejeite senão aceite."
Exemplo: n=5
] a a a a a F a a t ...
] X a a a a F a a t ...
] X a a a a F X a t ...
] X X a a a F X a t ...
] X X a a a F X X t ...
] X X a a a F a a t ...
] X X X a a F a a t ...
] X X X a a F X a t ...
Teoria 6
Máquina de Turing
Padronizar descrição informal de MT
Logo: A = {an| n é um número primo.}
Uma MT que decide A:
M="Sobre a entrada 〈N〉, ou seja an, n primo:
1 Gerar os inteiros k de 2 a n-1;
2 Determinar se k divide n, usando subtrações sucessivas.
3 Se algum k divide n rejeite senão aceite."
Exemplo: n=5
] a a a a a F a a t ...
] X a a a a F a a t ...
] X a a a a F X a t ...
] X X a a a F X a t ...
] X X a a a F X X t ...
] X X a a a F a a t ...
] X X X a a F a a t ...
] X X X a a F X a t ...
Teoria 6
Máquina de Turing
Padronizar descrição informal de MT
Logo: A = {an| n é um número primo.}
Uma MT que decide A:
M="Sobre a entrada 〈N〉, ou seja an, n primo:
1 Gerar os inteiros k de 2 a n-1;
2 Determinar se k divide n, usando subtrações sucessivas.
3 Se algum k divide n rejeite senão aceite."
Exemplo: n=5
] a a a a a F a a t ...
] X a a a a F a a t ...
] X a a a a F X a t ...
] X X a a a F X a t ...
] X X a a a F X X t ...
] X X a a a F a a t ...
] X X X a a F a a t ...
] X X X a a F X a t ...
Teoria 6
Máquina de Turing
Padronizar descrição informal de MT
Logo: A = {an| n é um número primo.}
Uma MT que decide A:
M="Sobre a entrada 〈N〉, ou seja an, n primo:
1 Gerar os inteiros k de 2 a n-1;
2 Determinar se k divide n, usando subtrações sucessivas.
3 Se algum k divide n rejeite senão aceite."
Exemplo: n=5
] a a a a a F a a t ...
] X a a a a F a a t ...
] X a a a a F X a t ...
] X X a a a F X a t ...
] X X a a a F X X t ...
] X X a a a F a a t ...
] X X X a a F a a t ...
] X X X a a F X a t ...
Teoria 6
Máquina de Turing
Padronizar descrição informal de MT
Logo: A = {an| n é um número primo.}
Uma MT que decide A:
M="Sobre a entrada 〈N〉, ou seja an, n primo:
1 Gerar os inteiros k de 2 a n-1;
2 Determinar se k divide n, usando subtrações sucessivas.
3 Se algum k divide n rejeite senão aceite."
Exemplo: n=5
] a a a a a F a a t ...] X a a a a F a a t ...
] X a a a a F X a t ...
] X X a a a F X a t ...
] X X a a a F X X t ...
] X X a a a F a a t ...
] X X X a a F a a t ...
] X X X a a F X a t ...
Teoria 6