PCS 2214 -Fundamentos de Engenharia de Computação I Professores:Ann, Notas de estudo de Engenharia Elétrica

Baixe PCS 2214 -Fundamentos de Engenharia de Computação I Professores:Ann e outras Notas de estudo em PDF para Engenharia Elétrica, somente na Docsity! 1 PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 1 PCS 2214 - Fundamentos de Engenharia de Computação I Professores: Anna Helena Reali Costa Jaime Simão Sichman Liria Matsumoto Sato Romero Tori 1o. Semestre 2005 MÁQUINA DE TURING PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 2 Conteúdo 1. Máquinas de Turing. 2. Ações de uma Máquina de Turing 3. Definição Formal de uma Máquina de Turing 4. Linguagens Decidíveis 5. Máquina de Turing para Computar Funções 6. Linguagens Formais e Modelos Computacionais 7. Tese de Church-Turing 2 PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 3 • Máquina de Turing: modelo mais poderoso de computador, proposto pelo inglês Alan M. Turing em 1936. • Similar a um autômato finito, porém com uma memória ilimitada e irrestrita, constituindo um modelo mais preciso de um computador de propósito geral. • Uma Máquina de Turing computa uma entrada. Máquina de Turing PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 4 Alan Mathison Turing (23/06/1912 – 07/06/1954) Matemático, lógico, criptógrafo e herói de guerra britânico. Considerado o pai da ciência da computação. Fez previsões acerca da Inteligência Artificial e propôs o Teste de Turing, contribuindo para o debate sobre a consciência das máquinas e suas capacidades de pensar. Formalizou o conceito de algoritmo e computação com a Máquina de Turing, gerando sua versão da Tese de Church- Turing. Responsável pela quebra do código alemão Enigma durante a II Guerra Mundial. Depois da guerra, projetou um pioneiro computador digital programável eletronicamente. Foi processado e condenado por ser homossexual (em 1952). Morreu envenenado (provável suicídio). O Turing Award foi criado em sua homenagem. 5 PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 9 • Ex: uma MT é definida pelo conjunto de quíntuplas: (0,0,1,0,D), (0,1,0,0,D), (0,b,1,1,E), (1,0,0,1,D), (1,1,0,1,D), (1,b,b,2,D). O estado de aceitação é 2. Verificar sua computação: 0 1 1 0 b . . . 0 (0,0,1,0,D) 0 1 1 1 0 b . . . (0,1,0,0,D) Início: Ações da Máquina de Turing PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 10 0 1 0 1 0 b . . . (0,1,0,0,D) 0 1 0 0 0 b . . . (0,0,1,0,D) 0 1 0 0 1 b . . . (0,b,1,1,E) (1,1,0,1,D) 1 1 0 0 1 1 . . . b Ações da Máquina de Turing 6 PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 11 (1,1,0,1,D) 1 1 0 0 0 1 . . . b Como a máquina pára no estado 2 (estado de aceitação), a fita terá: 1 1 0 0 0 0 . . . b 1 0 0 0 0 . . . b Ações da Máquina de Turing (1,b,b,2,D) 2 1 0 0 0 0 . . . b b PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 12 • Exercício: Considere a seguinte MT: (0,0,0,1,D), (0,1,0,0,D), (0,b,b,0,D), (1,0,1,0,D), (1,1,1,0,E). Qual o comportamento da MT quando iniciada com: Ações da Máquina de Turing 1 0 b . . . (a) 0 0 1 b . . . (b) 0 0 0 b . . . (c) 0 7 PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 13 Definição Formal da Máquina de Turing • Uma MT = (S, I, Γ, f, σ0, σA, σR) é: – Um conjunto finito S de estados; – Um conjunto finito I de símbolos de entrada, b ∉ I; – Um conjunto finito Γ de símbolos da fita, com b ∈ Γ e I ⊆ Γ; – Uma função f: S × Γ → S × Γ × {E, D}, sendo D:direita, E:esquerda; – σ0 ∈ S é o estado inicial; – σA ∈ S é o estado de aceitação; – σR ∈ S é o estado de rejeição, com σA ≠ σR . • OBS: b: célula em branco da fita PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 14 Diagrama de Transições de uma MT • Seja M = (S, I, Γ, f, σ0, σA, σR) uma máquina de Turing. O diagrama de transições de M é um grafo orientado G com: – vértices membros de S. – uma seta indica o estado inicial σ0. – uma aresta orientada (σ1,σ2) existe em G se existir uma entrada de fita i∈Γ com f(σ1,i)=(σ2, j, m), sendo σ1,σ2∈S, j∈Γ e m indica o movimento do cursor, m∈{E, D}. Neste caso, a aresta (σ1,σ2) é rotulada com i → j, m, para i ≠ j, e i → m se i = j. 10 PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 19 Linguagem Decidível • Ao iniciar uma MT com uma entrada, pode-se: aceitar a entrada ou não aceitar a entrada. • Uma MT pode não aceitar uma entrada: 1. ao entrar em σR e rejeitar a cadeia ou 2. ao entrar em loop infinito e não parar. – Pode ser muito difícil distinguir uma MT que entrou em loop infinito de outra que está demorando para computar. • Uma MT decide uma linguagem quando pára para todas as entradas: – se w ∉ L(M), MT pára em σR ; – se w∈ L(M), MT pára em σA . PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 20 Exemplo de MT • Projetar uma Máquina de Turing M que decide a linguagem A={0n1n | n>0}. • Algoritmo esquematizado de M: M=“para a cadeia de entrada w∈{0,1}*: 1. Se w = λ, rejeite. 2. Leia a célula corrente. Se 0, troque por X e vá para o passo 3. Se Y, procure o final da cadeia de Ys e aceite. Senão, rejeite. 3. Vá para a direita da fita, procurando o primeiro 1. Se encontrar, troque-o por Y e vá para o passo 4. Senão, rejeite. 4. Vá para a esquerda na fita, procurando por um X. Se encontrar, volte a avançar na fita e vá para o passo 2. Senão, rejeite.” 11 PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 21 Exemplo de MT • Descrição formal de M = (S, I, Γ, f, σ0, σA, σR): S = {A,B,C,D, σA, σR}, σ0 = A, I={0,1} , Γ= {0,1,X,Y,b}, f = diagrama de transições: • Represente esta máquina M por um conjunto de ações. D σRσA A B C0→X,D 0→D X→D Y→DY→D b→D 0→E,1→Y,E Y→E 1→D, b→D X→D, 1→D, X→D, b→D b→D 1→D, X→D, 0→D Y→D PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 22 • Um autômato finito é um caso muito particular de MT, que sempre imprime o símbolo lido na célula, sempre se move para a direita e sempre pára ao ler o símbolo b (término da cadeia). • Exercício: descreva o AF abaixo como uma MT Máquina de Turing e Autômato Finito 1 0 P I 1 0 12 PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 23 • Vimos que uma MT pode decidir uma linguagem. No entanto, uma MT também pode computar funções: Dada uma MT T e uma cadeia α, começamos com T na configuração inicial padrão em uma fita contendo α. Se T em algum momento pára deixando uma cadeia β na fita, podemos considerar β o valor de uma função avaliada em α. Assim, T(α) = β. O domínio da função T consiste de todas as cadeias α para as quais T, em algum momento, pára. Aplicações da Máquina de Turing PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 24 MT para Computar Funções • Exemplo: Projetar uma MT que calcule a subtração x − y, com x > y. Considere x e y em representação unária, fornecidos na fita da seguinte forma: 31111 .......... 2111 111 01 decimalunáriax – y b b b b b ........ MEF Ex: x=5, y=2 fita: 111111–111bbbb Resposta na fita: 1111bbbbb Modifique sua máquina para aceitar x ≥ y. 15 PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 29 Algoritmos e MTs • Noção intuitiva de algoritmo: é um conjunto finito de instruções que podem ser executadas mecanicamente em tempo finito para resolver algum problema. Com dados de entrada apropriados ao problema, o algoritmo tem que parar e produzir a resposta correta. • Portanto, qualquer função f computável por uma MT é uma função cujos valores podem ser encontrados por um algoritmo ou procedimento computacional. PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 30 Tese de Church-Turing • Em 1936, com os artigos publicados por Turing e Alonzo Church, é que se definiu claramente o que seria um algoritmo: é uma MT que pára em respostas a todas as entradas. • Tese de Church-Turing: “Qualquer função de teoria dos números é computável por um algoritmo se, e somente se, é computável por uma Máquina de Turing.” Computável por um algoritmo Computável por uma MT tese 16 PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 31 Alonzo Church (14/06/1903 – 11/08/1995) Matemático americano, responsável por alguns dos fundamentos da CC. Nasceu em Washington, DC, recebeu BA e PhD na Universidade de Princeton, USA, em 1924 e 1927, respectivamente. Tornou- se professor em Princeton em 1929. Foi orientador de Stephen C. Kleene (1909- 1994), entre outros. Também orientou Alan Turing de 1936 a1938. Seu trabalho mais conhecido é o desenvolvimento do cálculo-λ no seu famoso artigo de 1936, mostrando a existência de problemas indecidíveis. Ele e Turing mostraram que o cálculo-λ e a MT são equivalentes em capacidades, resultando na tese de Church-Turing. Como há disputa sobre “quem foi o primeiro”, esta tese também é conhecida como tese de Church e tese de Turing. PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo: Máquina de Turing Autora: Anna H. R. Costa Versão: 2.0 Data: 25/05/05 32 Principal: Sipser, M. Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA. 1997. Auxiliares: Johnsonbaugh, R. Discrete Mathematics. Prentice Hall International, London, UK, 4th. Ed. 1997. Cap. 10. Gersting, J.L. Fundamentos Matemáticos para a Ciência da Computação. LTC Editora, Rio de Janeiro. 5a. Edição. 2004. Cap. 8. Lewis, H.R. and Papadimitriou, C.H. Elementos de Teoria da Computação. Bookman, Porto Alegre. 2a. Edição, 2004. Bibliografia