Baixe o app para aproveitar ainda mais
Prévia do material em texto
Informática Teórica Engenharia da Computação MÁQUINAS DE TURING Máquinas de Turing - História (1900) – David Hilbert – Apresentou 23 problemas que deveriam ser resolvidos no próximo século. – 10º problema: Encontrar um processo com o qual é possível determinar se um polinômio tem uma raiz inteira, usando um número finito de operações; Algoritmo; Máquinas de Turing - História Início do século XX: pesquisas com o objetivo de definir – modelo computacional suficientemente genérico – capaz de implementar qualquer função computável Máquinas de Turing - História (1936) – Alan Turing – Propôs um modelo matemático do processo de computação; – Máquina de Turing; – aceito como uma formalização de: procedimento efetivo algoritmo ou função computável Máquinas de Turing - História (1936) – Alonzo Church – Apresentou sua hipótese que qualquer função computável pode ser processada por uma máquina de Turing. – existe um procedimento expresso na forma de uma máquina de Turing capaz de processar qualquer função computável; – como a noção intuitiva de procedimentos não é matematicamente precisa impossível demonstrar formalmente se a máquina de Turing é, de fato, o mais genérico dispositivo de computação; mostrado: todos os demais modelos propostos possuem, no máximo, a mesma capacidade computacional; Máquinas de Turing Resumidamente, uma Máquina de Turing – Semelhante a um autômato; – Mas com uma memória ilimitada e irrestrita; – Utiliza uma fita que não possui tamanho máximo; – Pode ser usada simultaneamente como dispositivo de entrada, de saída e de memória de trabalho; Hierarquia de Chomsky Linguagens Recursivamente Enumeráveis(0) Linguagens Sensíveis ao Contexto (1) Linguagens Livre de Contexto (2) Linguagens Regulares (3) Hierarquia de Chomsky Hierarquia Linguagem Gramática Reconhecedor Tipo-0 [0] Linguagens Recursivamente Enumeráveis Gramáticas Irrestritas Máquina de Turing Tipo-1 [1] Linguagens Sensíveis ao Contexto Gramáticas Sensíveis ao Contexto Máquina de Turing Com fita limitada Tipo-2 [2] Linguagens Livres de Contexto Gramáticas Livres de Contexto Autômato com Pilha Tipo-3 [3] Linguagens Regulares Gramáticas Regulares Autômato Finito Linguagens Recursivamente Enumeráveis ou Tipo 0 aceitas por uma máquina de Turing segundo a Hipótese de Church, a Classe das Linguagens Recursivamente Enumeráveis – conjunto de todas as linguagens – que podem ser reconhecidas mecanicamente – em um tempo finito Linguagens Recursivamente Enumeráveis ou Tipo 0 inclui algumas para as quais é – impossível determinar mecanicamente – se uma palavra não pertence à linguagem se L é uma destas linguagens, então – para qualquer máquina de Turing M que aceita L – existe pelo menos uma palavra w não pertencente a L que – ao ser processada por M, a máquina entra em loop infinito ou seja – se w pertence a L, M pára e aceita a entrada – se w não pertence a L, M pode parar, rejeitando a palavra ou permanecer processando indefinidamente Linguagens Recursivas subclasse da Classe das Linguagens Enumeráveis Recursivamente existe pelo menos uma máquina de Turing que para em qualquer entrada, aceitando ou rejeitando Máquina de Turing Máquina de Turing (Alan Turing, 1936) – mecanismo simples – formaliza a ideia de uma pessoa que realiza cálculos – lembra os computadores atuais embora proposta anos antes do primeiro computador digital Modelo máquina de Turing – no mínimo, mesmo poder computacional – de qualquer computador de propósito geral Máquina de Turing Modelo muito mais preciso de um computador de propósito geral; Pode fazer tudo que um computador real pode fazer; – Entretanto, não pode resolver alguns problemas Estão além dos limites teóricos da computação. Máquina de Turing Usa uma fita infinita com sua memória ilimitada; Ela tem uma cabeça que pode ler e escrever símbolos e mover sobre a fita; Inicialmente a fita contém somente a cadeia de entrada e está em branco em todo o restante; Poder ler ou escrever informação na fita; Máquina de Turing - Modelo Constituído de três partes Fita, usada simultaneamente como dispositivo de – entrada, saída e memória de trabalho Unidade de Controle – reflete o estado corrente da máquina – possui uma unidade de leitura e gravação (cabeça da fita) – acessa uma célula da fita de cada vez – se movimenta para a esquerda ou para a direita Programa, Função Programa ou Função de Transição – define: estado da máquina – comanda: leituras, gravações e sentido de movimento (cabeça) Máquina de Turing - Modelo Fita: finita à esquerda e infinita à direita – infinita: “tão grande quanto necessário” – dividida em células, cada uma armazenando um símbolo Símbolos podem – pertencer ao alfabeto de entrada – pertencer ao alfabeto auxiliar – ser "branco" Máquina de Turing - Modelo Máquina de Turing Unidade de controle – número finito e predefinido de estados – cabeça da fita lê um símbolo de cada vez e grava um novo símbolo move uma célula para a direita ou para a esquerda – símbolo gravado e o sentido do movimento definidos pelo programa Máquina de Turing - Exemplo Seja B = {w#w | w {0,1}*}. Queremos que M1 aceite se sua entrada é um membro de B e rejeite caso contrário. – Ela realiza múltiplas varridas sobre a cadeia de entrada com a cabeça de leitura-escrita. – A cada passagem ela emparelha um dos caracteres em cada lado do símbolo #. – Para manter registro de quais símbolos já foram verificados, M1 deixa uma marca sobre cada símbolo à medida que ele é examinado. – Se ela marca todos os símbolos, isso significa que tudo emparelhou de forma bem sucedida, e M1 vai para um estado de aceitação; – Se ela descobre uma sobra, ela entra em um estado de rejeição. Máquina de Turing - Exemplo Em resumo, o algoritmo de M1 é o seguinte: – 1. Faça um varredura na entrada para assegurar que ela contém uma única ocorrência do símbolo #. Se não, rejeite. – 2. Faça um zigue-zague na fita para fazer corresponder posições nos dois lados do símbolo # para verificar se essas posições contém o mesmo símbolo. Se elas não contêm, rejeite. Marque os símbolos à medida que eles são verificados para manter registro de quais símbolos têm correspondência. – 3. Quando todos os símbolos à esquerda do # foram marcados, verifique se existe algum símbolo remanescente à direita do #. Se quaisquer símbolos restam, rejeite; caso contrário, aceite. Máquina de Turing - Exemplo Máquina de Turing – Definição Formal M = (Q, Σ, Γ, δ, q0,qa, qr) – Q - conjunto de estados possíveis da máquina (finito) – Σ - alfabeto (de símbolos) de entrada Não contém o símbolo especial Branco (β) – Γ - alfabeto da fita Onde β ϵ Γ e Σ C Γ – δ - (função) programa ou função de transição δ: Q × Γ → Q × Γ × { E, D } transição da máquina: δ(p, x) = (q, y, E) – q0 - estado inicial – qa – estado de aceitação – qr – estado de rejeição Máquina de Turing – Definição Formal Função de Transição – É o coração da definição de uma MT; – Ela diz como a máquina vai de um estado para outro; δ(p, x) = (q, y, E) – δ(p, x) considera estado corrente símbolo lido da fita – (q, y, E) determina novo estado símbolo a ser gravado sentido de movimento da cabeça (E e D) Máquina de Turing – Definição Formal Função de Transição – suponha a transição δ(p, x) = (q, y, m) Máquina de Turing – Exemplo Descreva uma MT que reconheça a linguagem L = { 𝒂𝒏𝒃𝒏 | n ≥ 0 } – Estratégia: a MT trocará um a por um A, e depois um b por um B, até todos os a’s e b’s terem sido comparados. – Em cada passo, da esq. para dir., ela troca um a por A e vai para a direita, ignorando a’s e B’s até encontrar b. Troca esse b por B e se move para a esquerda, ignorando B’s e a’s, até encontrar um A. Procura um a a direita e troca por A, repetindo o processo. – Se a entrada não estiver em 𝒂𝒏𝒃𝒏 eventualmente a MT não vai ter um movimento previsto e vai parar sem aceitar. – Se, por outro lado, na busca por mais um a, ela só encontrar A’s e B’s, então ela descobre que deve aceitar a entrada. Máquina de Turing – Exemplo Descreva uma MT que reconheça a linguagem L = { 𝒂𝒏𝒃𝒏 | n ≥ 0 } – M = ({q0,q1,q2,q3,qa}, {a,b}, {a,b,A,B,β}, δ, q0, {qa}) Estado a b A B β q0 (q1,A,D) (q3,B,D) (qa, β, D) q1 (q1,a,D) (q2,B,E) (q1,B,D) q2 (q2,a,E) (qo,A,D) (q2,B,E) q3 (q3,B,D) (qa, β,D) qa Máquina de Turing – Exemplo Descreva uma MT que reconheça a linguagem L = { 𝒂𝒏𝒃𝒏 | n ≥ 0 } – M = ({q0,q1,q2,q3,qa}, {a,b}, {a,b,A,B, β}, δ, q0, {qa}) (B, B, D) (β, β, D) q0 (a, A, D) q1 (a, a, D) (B, B, D) q2 (b, B, E) (a, a, E) (B, B, E) (A, A, D) q3 (B, B, D) qa (β, β, D) Máquina de Turing – Exemplo B D ᶸ D q0 a A , D q1 a,B D q2 b B,E a,B E A D q3 B D qa ᶸ D Descreva uma MT que reconheça a linguagem L = { 𝒂𝒏𝒃𝒏 | n ≥ 0 } – M = ({q0,q1,q2,q3,qa}, {a,b}, {a,b,A,B, β}, δ, q0, {qa}) Máquina de Turing – Exemplo Descreva uma MT que reconheça a linguagem L = { 𝒂𝒏𝒃𝒏 | n ≥ 0 } – M = ({q0,q1,q2,q3,qa}, {a,b}, {a,b,A,B, β}, δ, q0, {qa}) (β, β, D) (a, A, D) (a, a, D) (B, B, D) (b, B, E) (a, a, E) (B, B, E) (A, A, D) (B, B, D) a A , D a,B E b B,E a,B D A D B D β D Máquina de Turing – Configuração Quando uma MT computa, mudanças ocorrem: – No estado atual; – No conteúdo da fita; – E na localização da cabeça; A combinação dessas três informações é chamada configuração de uma MT. – Para um estado q e duas cadeias u e v sobre o alfabeto da fita Γ, – Escrevemos uqv para a configuração onde o estado atual é q, o conteúdo da fita é uv, e a localização da cabeça é o primeiro símbolo de v. Máquina de Turing – Configuração Configuração inicial de uma MT M – q0w – Sobre a entrada w Configuração de aceitação -> qaceita Configuração de rejeição -> qrejeita Uma MT aceita a entrada w, se uma sequência de configurações 𝑪𝟏, 𝑪𝟐, ..., 𝑪𝒌 existe, onde: 1. 𝑪𝟏 é a configuração inicial de M sobre a entrada w 2. Cada 𝑪𝒊 produz 𝑪𝒊+𝟏, e; 3. 𝑪𝒌 é uma configuração de aceitação Máquina de Turing – Configuração Exemplo: configuração 1011q701111 1011q701111 Exemplo Uma MT para aceitar {anbn | n 0} a ᶸbba ᶸ ... B D ᶸ D q0 a A , D q1 a,B D q2 b B,E a,B E A D q3 B D qa ᶸ D qoaabb Aq1abb Aaq1bb Aq2aBb q2AaBb Aq0aBb AAq1Bb AABq1b Aq2ABB AAq2BB AAq0BB AABq3B AABBq3 AABBqa Exemplo Uma MT para aceitar {anbn | n 0} a ᶸbba ᶸ ... Máquina de Turing – Definição Definição: Chame uma linguagem Turing-reconhecível ou Recursivamente Enumerável se alguma máquina de Turing a reconhece. Quando iniciamos uma MT sobre uma entrada, três resultados são possíveis. A máquina pode – Aceitar; – Rejeitar; – ou entrar em loop. Uma MT pode falhar em aceitar uma cadeia entrando no estado qrejeita e rejeitando, ou entrando em loop. Distinguir uma MT que está em loop de uma que está levando um tempo longo é difícil. Máquina de Turing – Definição Por essa razão preferimos MT’s que parem sobre todas as entradas; – Tais MT’s nunca entram em loop Essas máquinas são chamadas decisores, pois sempre tomam uma decisão de aceitar ou rejeitar. – Um decisor que reconhece uma linguagem é dito decidir aquela linguagem. Definição: Chame uma linguagem Turing-decidível ou simplesmente decidível se alguma máquina de Turing a decide; – Também chamada de linguagem recursiva; Máquina de Turing – Exemplo Uma MT que reconheça a linguagem L = {02 𝑛 | 𝑛 ≥ 0} Estágios para a resolução: – 0. Marque o primeiro zero com Y; – 1. Atravesse da esquerda para direita marcando um zero sim outro não com um X; – 2. Se no estágio 1. a fita contém 1 único 0 aceite. Se contiver mais do que 1 zero e o número for impar, rejeite. – 3. Retorne ao marcador Y; – 4. Vá para o estágio 1; Máquina de Turing – Exemplo M2 = (Q, Σ, Γ, δ, q1,qaceita, qrejeita) Q = {q1, q2 , q3 , q4 , q5 , qaceita, qrejeita}, Σ = {0}, e Γ = {0, X, Y, } П q2 qaceitaqrejeita q3 0 X , D q5 0 D q1 0 Y , D X D q4 X D Máquina de Turing – Exercício Uma MT que reconheça a linguagem L = {02 𝑛 | 𝑛 ≥ 0} 0 X, Dᶸ D 0 E X E X D ᶸ D X D ᶸ D Máquina de Turing – Exemplo Uma MT que reconheça a linguagem L = {02 𝑛 | 𝑛 ≥ 0} Exercício: mostre as configurações da MT acima para a entrada 0000 Exercício: mostre as configurações da MT acima para a entrada 00000 Máquinas de Turing Descrevemos uma MT M1 bem simples que faz a concatenação de dois inteiros positivos, representados por * e separados por um branco na fita. * ᶸ***ᶸ**** ᶸ ... Exemplo q0 Ler os * movendo a fita para a direita, ao encontrar o branco escrever *, move para a direita, vai para estado q1 q1 Ler os * ,move para a direita, continuar no estado 1 até encontrar um branco (fim da fita), mover para esquerda, ir para estado 2 q2 Apagar * e ir para um estado de aceitação. * ᶸ***ᶸ**** ᶸ ... q0 * D ᶸ * , D q1 * D ᶸ E q2 * ᶸ , D qa Vídeo: https://www.youtube.com/watch?v=E3keLeMwfHY
Compartilhar