TeoriaCaomputacao e Book

1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

1 INTRODUO E CONCEITOS BSICOS Inicia com uma breve histria do surgimento e do desenvolvimento dos conceitos, resultados e formalismos nos quais a Teoria da Computao baseada.

Formalizao dos conceitos de programa e de mquinaExistem diferentes computadores, com diferentes arquiteturas, e existem diversos tipos de linguagens de programao, Modelos matemticos simples. Programas e mquinas so tratados como entidades distintas, mas complementares e necessrias para a definio de computao.

1.1 Notas Histricas

Cincia da Computao o conhecimento sistematizado relativo computao. Na antiga Grcia (sculo III A.C., no desenho de algoritmos por Euclides) Na Babilnia (complexidade\reducibilidade problemas). Interesse atual possui duas nfases:

nfase terica - idias fundamentais e modelos computacionais: da biologia (modelos para redes de neurnios), da eletrnica (teoria do chaveamento), da matemtica (lgica), da lingstica (gramticas para linguagens naturais). nfase prtica - projeto de sistemas computacionais aplicando a teoria prtica.

No incio do sculo XX, diversas pesquisas foram desenvolvidas com o objetivo de definir um modelo computacional suficientemente genrico, capaz de implementar qualquer Funo Computvel.

____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 1

1 INTRODUO E CONCEITOS BSICOS_________________________________________________________________________________________

Um marco inicial da Teoria da Computao - David Hilbert, Entscheidungsproblem, o qual consistia em encontrar um procedimento para demonstrar se uma dada frmula no clculo de preposies de primeira ordem era vlida ou no. (Frmula do clculo de predicados no qual a quantificao restrita s variveis individuais) Em 1931, Kurt Gdel - Incompleteness Theorem (teorema da no completude), onde demonstrou que tal problema (mecanizao do processo de prova de teoremas) no tinha soluo. A classe de funes usada por Gdel foi a das funes primitivas recursivas definidas anteriormente por Dedekind em 1888. Embora no tenha sido proposital, Gdel foi (aparentemente) o primeiro a identificar um formalismo para definir a noo de procedimento efetivo. Em 1936, Church usou dois formalismos para mostrar que o problema de Hilbert no tem soluo: -calculus (Church, 1936) e funes recursivas (Kleene, 1936).Procedimentos efetivos - So caracterizaes to gerais da noo do efetivamente computvel quanto consistentes com o entendimento intuitivo usual (Church).

Turing props, em 1936, um formalismo para a representao de procedimentos efetivos. Esse foi o primeiro trabalho a identificar programas escritos para uma mquina computacional autmata, como noes intuitivas de efetividade.____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 2

1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Desde ento, muitos outros formalismos foram propostos, os quais possuem o mesmo poder computacional que as funes recursivas (ou Clculo Lambda): Mquina de Turing (1936); Sistema Cannico de Post (1943); Algoritmo de Markov e a Linguagem Snobol (1954); Mquinas de Registradores (1963); RASP (Random Acess Stored Programs - 1964). Programa definido como sendo um procedimento efetivo, pode ser descrito usando qualquer dos formalismos equivalentes. Ou seja, qualquer destes formalismos permite descrever todos os procedimentos possveis que podem ser executados em um computador.

1.2 AbordagemA abordagem desse livro combina a abordagem histrica com abordagens prximas dos sistemas computacionais modernos. Parte dessa abordagem inspirada, entre outros, no trabalho de Richard Bird em Programs and Machines- An Introduction to the Theory of Computation ([BIR76]).



1.3 Conceitos BsicosLinguagem um conceito fundamental no estudo da Teoria da Computao, pois trata-se de uma forma precisa de expressar problemas, permitindo um desenvolvimento formal adequado ao estudo da computabilidade. O dicionrio Aurlio define linguagem como: "o uso da palavra articulada ou escrita como meio de expresso e comunicao entre pessoas". Esta definio no suficientemente precisa para permitir o desenvolvimento matemtico de uma teoria sobre linguagens. As definies que seguem so construdas usando como base a noo de Smbolo ou Caractere, que uma entidade abstrata bsica, no sendo definida formalmente. Letras e dgitos so exemplos de smbolos freqentemente usados. Definio 1.1 Alfabeto. Um Alfabeto um conjunto finito de smbolos ou caracteres. um conjunto infinito no um alfabeto: o conjunto vazio um alfabeto. Exemplo 1.1 Os seguintes conjuntos so exemplos de alfabetos: {a, b, c}; conjunto vazio. Os seguintes conjuntos no so exemplos de alfabetos: conjunto dos nmeros naturais; {a, b, aa, ab, ba, bb, aaa,...}.____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 4

1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Definio 1.2 Cadeia de Smbolos, Palavra. Uma Cadeia de Smbolos sobre um conjunto uma seqncia de zero ou mais smbolos (do conjunto) justapostos. Uma Cadeia de Smbolos Finita usualmente denominada de Palavra. denota a cadeia vazia ou palavra vazia. Se representa um conjunto de smbolos (um alfabeto), * => o conjunto de todas as palavras possveis sobre ; + denota * - { }. Definio 1.3 Comprimento ou Tamanho de uma Palavra. O Comprimento ou Tamanho de uma palavra w, representado por w, o nmero de smbolos que compem a palavra. Definio 1.4 Prefixo, Sufixo, Subpalavra. Um Prefixo (respectivamente, Sufixo) de uma palavra qualquer seqncia inicial (respectivamente, final) de smbolos da palavra. Uma Subpalavra de uma palavra qualquer seqncia de smbolos contga da palavra. Exemplo 1.2 Palavra, Prefixo, Sufixo, Tamanho.a) b) abcb uma palavra sobre o alfabeto {a, b, c}; Se = {a, b}, ento: + = {a, b, aa, ab, ba, bb, aaa,...} * = { , a, b, aa, ab, ba, bb, aaa,...} abcb = 4 e = 0; Relativamente palavra abcb, tem-se que: , a, ab, abc, abcb so os prefixos; , b, cb, bcb, abcb so os respectivos sufixos. Qualquer prefixo ou sufixo de uma palavra uma sub-palavra.

c) d)

e)



Definio 1.5 Linguagem Formal Uma Linguagem Formal ou simplesmente Linguagem um conjunto de palavras sobre um alfabeto. Exemplo 1.3 Linguagem Formal. Suponha o alfabeto = {a, b}. Ento: a) O conjunto vazio e o conjunto formado pela palavra vazia so linguagens sobre . Obviamente, { } { }. b) O conjunto de palndromos (palavras que tm a mesma leitura da esquerda para a direita e vice-versa) sobre um exemplo de linguagem infinita. , a, b, aa, bb, aaa, aba, bab, bbb, aaaa,... Definio 1.6 Concatenao de Palavras. A Concatenao de Palavras uma operao binria, definida sobre uma linguagem L, a qual associa a cada par de palavras uma palavra formada pela justaposio da primeira com a segunda tal que: no necessariamente fechada em L; a concatenao de duas palavras de uma linguagem no necessariamente resulta em uma palavra da linguagem. associativa; v(wt) = (vw)t = vwt possui elemento neutro esquerda e direita, o qual a palavra vazia. w = w = w Exemplo 1.4 Concatenao de Palavras. Suponha o alfabeto = {a, b}. Ento, para as palavras v = baaaa e w = bb, tem-se que: vw = baaaabb v = v = baaaa____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 6

1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Definio 1.7 Concatenao Sucessiva de uma Palavra. A Concatenao Sucessiva de uma Palavra (com ela mesma) ou simplesmente Concatenao Sucessiva, representada na forma de um expoente (suponha w uma palavra): wn onde n o nmero de concatenaes sucessivas,

definida indutivamente a partir da operao de concatenao binria, como segue: w0 = ; wn = wn-1w, para n > 0. Exemplo 1.5 Concatenao Sucessiva. Sejam w uma palavra e a um smbolo. Ento: w3 = www w1 = w a5 = aaaaa an = aaa...a (o smbolo a repetido n vezes)



1.4 ExercciosExerccio 1.1 Elabore uma linha de tempo sobre o desenvolvimento do conceito de funo computvel. Exerccio1.2 Qual o marco inicial da Teoria da Computao? Exerccio 1.3 Em que se consistia o problema de Hilbert Entscheidungsproblem e por que ele sem soluo? Exerccio 1.4 Qual a importncia da Hiptese de Church e porque ela no demonstrvel? Exerccio 1. 5 Marque os conjuntos que so alfabetos: a) Conjunto dos nmeros naturais; [ ] b) c) d) e) f) g) h) i) Conjunto dos nmeros primos; [ ] Conjunto das letras do alfabeto brasileiro; [ ] Conjunto dos algarismos arbicos; [ ] Conjunto dos algarismos romanos; [ ] Conjunto { a, b, c, d }; [ ] Conjunto das partes de { a, b, c }; [ ] Conjunto das vogais; [ ] Conjunto das letras gregas. [ ]

Exerccio 1.6 D os possveis prefixos e sufixos de cada uma das seguintes palavras: a) teoria b) universidade c) aaa d) abccba e) abcabc Exerccio 1.7 Demonstre ou negue as seguintes propriedades algbricas da operao de concatenao de palavras: a) Fechamento b) Comutatividade c) Existncia de elemento neutro d) Associatividade Exerccio 1.8 Quando se pode dizer que a estrutura algbrica da operao de concatenao de palavras de uma linguagem anloga estrutura da operao de adio nos naturais? Teorema 4. ____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 8

1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Teorema 4.2 PROGRAMAS, MQUINAS E COMPUTAES

2.1 Programas 2.1.1 Programa Monoltico 2.1.2 Programa Iterativo 2.1.3 Programa Recursivo 2.2 Mquinas 2.3 Computaes e Funes Computadas 2.3.1 Computao 2.3.2 Funo Computada 2.4 Equivalncias de Programas e Mquinas 2.4.1 Equivalncia Forte de Programas 2.4.2 Equivalncia de Programas 2.4.3 Equivalncia de Mquinas 2.5 Verificao da Equivalncia Forte de Programas 2.5.1 Mquina de Traos 2.5.2 Instrues Rotuladas Compostas 2.5.3 Equivalncia Forte de Programas Monolticos 2.6 Concluso



Teorema 4.2 PROGRAMAS, MQUINAS E COMPUTAES

Definio 4.Formalizao dos conceitos

Existem diferentes computadores, com diferentes arquiteturas e existem diversos tipos de linguagens de programao, Modelos matemticos simples. Programas e mquinas so tratados como entidades distintas, mas complementares e necessrias para a definio de computao. O conceito de programa um conjunto de operaes e testes compostos de acordo com uma estrutura de controle. O tipo de estrutura de controle associada determina uma classificao de programas como: monoltico: baseada em desvios condicionais e incondicionais; iterativo: possui estruturas de iterao de trechos de programas; recursivo: baseado em sub-rotinas recursivas. O conceito de mquina interpreta os programas de acordo com os dados fornecidos. capaz de interpretar um programa desde que possua uma interpretao para cada operao ou teste que constitui o programa.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Computao e funo computada. Computao um histrico do funcionamento da mquina para o programa, considerando um valor inicial. Funo computada uma funo (parcial) induzida a partir da mquina e do programa dados. definida sempre que, para um dado valor de entrada, existe uma computao finita (a mquina pra).Definio 4.Equivalncia de programas e de mquinas

programas equivalentes fortemente: se as correspondentes funes computadas coincidem para qualquer mquina; programas equivalentes: se as correspondentes funes computadas coincidem para uma dada mquina; mquinas equivalentes: se as mquinas podem simular umas s outras. Resumo:Programa Mquina

Computao

Funo Computada

Equivalncia de Programas

Equivalncia de Mquinas

Classe de Funes Computveis

Mquina Universal



2.1 ProgramasUm programa pode ser descrito como um conjunto estruturado de instrues que capacitam uma mquina aplicar sucessivamente certas operaes bsicas e testes em uma parte determinada dos dados iniciais fornecidos, at que esses dados tenham se transformado numa forma desejvel. Estrutura de controle de operaes e testes. Estruturao Monoltica. baseada em desvios condicionais e incondicionais, no possuindo mecanismos explcitos de iterao, sub-diviso ou recurso. Estruturao Iterativa. Possui mecanismos de controle de iteraes de trechos de programas. No permite desvios incondicionais. Estruturao Recursiva. Possui mecanismos de estruturao em sub-rotinas recursivas. Recurso uma forma indutiva de definir programas. Tambm no permite desvios incondicionais.Definio 4.Composio

de Instrues Composio Seqencial. A execuo da operao ou teste subseqente somente pode ser realizada aps o encerramento da execuo da operao ou teste anterior. Composio No-Determinista. Uma das operaes (ou testes) compostas escolhida para ser executada. Composio Concorrente. As operaes ou testes compostos podem ser executados em qualquer ordem, inclusive simultaneamente. Ou seja, a ordem de execuo irrelevante.

No necessrio saber qual a natureza precisa das operaes e dos testes que constituem as instrues. Sero conhecidas pelos seus nomes. Identificadores de Operaes: F, G, H, ... Identificadores de Testes: T1, T2, T3, ... um teste uma operao de um tipo especial a qual produz somente um dos dois possveis valores verdade, ou seja, verdadeiro ou falso, denotados por: v e f, respectivamente. uma operao que no faz coisa alguma, denominada: operao vazia, denotada pelo smbolo .____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 12

Instrues: Operaes e Testes.

1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

2.1.1 Programa Monoltico

Um programa monoltico estruturado, usando desvios condicionais e incondicionais, no fazendo uso explcito de mecanismos auxiliares de programao. A lgica distribuda por todo o bloco (monlito) que constitui o programa. Fluxogramas uma das formas mais comuns de especificar programas monolticos; um diagrama geomtrico construdo a partir de componentes elementares denominados

partida

parada

operao

v

teste

f

No caso da operao vazia , o retngulo correspondente operao pode ser omitido, resultando simplesmente em uma seta.



EXEMPLO 2.1 Fluxogramapartida

F

T1 f G

v

f

T2 v parada

Definio 4.Instrues rotuladas

Fluxogramas podem ser reescritos na forma de texto, usando instrues rotuladas. So utilizados rtulos. Uma instruo rotulada pode ser: a) Operao. Indica a operao a ser executada seguida de um desvio incondicional para a instruo subseqente. b) Teste. Determina um desvio condicional, ou seja, que depende da avaliao de um teste. c) Uma parada especificada usando um desvio incondicional para um rtulo sem instruo correspondente. d) Assume-se que a computao sempre inicia no rtulo 1: 1: 2: 3: 4: faa F v_para 2 se T1 ento v_para 1 seno v_para 3 faa G v_para 4 se T2 ento v_para 5 seno v_para 1 Figura 2.3 Instrues rotuladas

Formalizao de Programa Monoltico____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 14

1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

A definio formal de Programa Monoltico melhor descrita, usando a notao de instrues rotuladas do que diagramas geomtricos. Definio 2.1 Rtulo, Instruo Rotulada. a) Um Rtulo ou Etiqueta uma cadeia de caracteres finita constituda de letras ou dgitos. b) Uma Instruo Rotulada i uma seqncia de smbolos de uma das duas formas a seguir (suponha que F e T so identificadores de operao e teste, respectivamente e que r1, r2 e r3 so rtulos): b.1) Operao r1: faa F v_para r2 b.2) Teste r1: se T ento v_para r2 seno v_para r3 Exemplo: r1: faa v_para r2 Definio 2.2 Programa Monoltico. Um Programa Monoltico P um par ordenado P = (I, r) onde: I Conjunto de Instrues Rotuladas o qual finito; r Rtulo Inicial o qual distingue a instruo rotulada inicial em I. Sabe-se que no conjunto dos Rtulos I no existem duas instrues diferentes com um mesmo rtulo; um rtulo referenciado por alguma instruo o qual no associado a qualquer instruo rotulada dito um Rtulo Final. A definio de Programa Monoltico requer a existncia de pelo menos uma instruo, identificada pelo rtulo inicial.

Observao 2.3 Programa Monoltico Fluxograma. Como um programa monoltico definido usando a noo de fluxograma, ambos os termos so identificados e usados indistintamente.



2.1.2 Programa Iterativo

Programas iterativos so baseados em trs mecanismos de composio (seqenciais) de programas, os quais podem ser encontrados em um grande nmero de linguagens de alto nvel, como, por exemplo, Algol 68, Pascal, e Fortran 90. seqencial: composio de dois programas, resultando em um terceiro, cujo efeito a execuo do primeiro e, aps, a execuo do segundo programa componente; condicional: composio de dois programas, resultando em um terceiro, cujo efeito a execuo de somente um dos dois programas componentes, dependendo do resultado de um teste; enquanto: composio de um programa, resultando em um segundo, cujo efeito a execuo, repetidamente, do programa componente enquanto o resultado de um teste for verdadeiro. at: anloga composio enquanto, excetuando que a execuo do programa componente ocorre enquanto o resultado de um teste for falso.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Formalizao de Programa IterativoDefinio 2.4 Programa Iterativo Um Programa Iterativo P indutivamente definido por: a) A operao vazia constitui um programa iterativo; b) Cada identificador de operao constitui um programa iterativo; c) Composio Seqencial. V;W

T ento V seno W) e) Composio Enquanto. enquanto T faa (V)resulta no programa que testa T e executa V, repetidamente, enquanto o resultado do teste for o valor verdadeiro. f) Composio At. at T faa (V) resulta no programa que testa T e executa V, repetidamente, enquanto o resultado do teste for o valor falso. Os parnteses foram utilizados nas clusulas das demais composies para possibilitar a interpretao, de forma unvoca, por partes consistentes. enquanto T faa V;W admite duas interpretaes distintas,

d) Composio Condicional (se

(enquanto T faa V);W enquanto T faa (V;W)

V

v

T

f

Figura 2.4 - Fluxograma que simula a composio enquanto



EXEMPLOS de Programas Iterativos a) A operao vazia constitui um programa iterativob) O programa abaixo do tipo iterativo. O uso de certa forma abusivo de linhas e identao objetiva facilitar a identificao visual da estruturao do programa.

(se T1 ento enquanto T2 faa (at T3 faa (V;W)) seno ()) Os programas tipo while de Bird so exemplos de programas iterativos. A traduo de Programas iterativos para Monolticos muito intuitiva, da mesma forma que a traduo de programa while para fluxograma intuitiva. Tem-se que a classe de funes computadas por programas while uma subclasse das funes computadas por fluxogramas.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

2.1.3 Programa RecursivoEu sou voc amanh, digo, uma recurso adiante

Recurso uma forma indutiva de definir programas. Sub-rotinas permitem a estruturao hierrquica de programas, possibilitando nveis diferenciados de abstrao.Conjunto de Identificadores de Sub-Rotinas - R1, R2, ..

Definio 2.5 Expresso de Sub-Rotinas. Uma Expresso de Sub-Rotinas (Expresso) E, definida indutivamente por:a) A operao vazia constitui uma expresso de sub-rotinas. b) Cada identificador de operao constitui uma expresso de sub-rotinas. c) Cada identificador de sub-rotina constitui uma expresso de sub-rotinas. d) A Composio Seqencial. Para D1 e D2 expresses de sub-rotinas, a composio seqencial denotada por: D1;D2 resulta em uma expresso de subrotina cujo efeito a execuo de D1 e, aps, a execuo de D2. e) A Composio Condicional. Se D1 e D2 so expresses de sub-rotinas e T um identificador de teste, ento a composio condicional denotada por: (se T ento D1 seno D2) resulta em uma expresso cujo efeito a execuo de D1 se T verdadeiro ou D2 se T falso.



Definio 2.6 - Programa Recursivo. Um Programa Recursivo P tem a seguinte forma:

P E0 onde R1 def E1, R2 def E2, ..., Rn def Enonde (suponha k {1, 2, ..., n}): E0 Expresso Inicial a qual uma expresso de sub-rotinas; Ek Expresso que Define Rk, a expresso que define a sub-rotina identificada por Rk. A operao vazia constitui um programa recursivo que no faz coisa alguma. EXEMPLO 2.6 Programa Recursivo.

P R;S onde R def F;(se T ento R seno G;S), S def (se T ento seno F;R)Figura 2.6 - Programa recursivo A computao de um programa recursivo consiste na avaliao da expresso inicial onde cada identificador de sub-rotina referenciado substitudo pela correspondente expresso que o define, e assim sucessivamente, at que seja substitudo pela expresso vazia , determinando o fim da recurso. At agora, foram definidos trs tipos de programas. Entretanto, esses programas so incapazes de descrever uma computao, pois no se tem a natureza das operaes ou dos testes, mas apenas um conjunto de identificadores. A natureza das operaes e testes especificada na definio de mquina.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

2.2 MquinasA mquina deve suprir todas as informaes necessrias para que a computao de um programa possa ser descrita: cada identificador de operao deve caracterizar uma transformao na estrutura da memria da mquina; cada identificador de teste interpretado pela mquina deve ser associado a uma funo verdade; nem todo identificador de operao ou teste definido em uma mquina; para cada identificador de operao ou teste definido em uma mquina, existe somente uma funo associada; deve descrever o armazenamento ou a recuperao de informaes na estrutura de memria.

Uma Mquina uma 7-uplaV X Y M = (V, X, Y, X, Y, F, T) Conjunto de Valores de Memria; Conjunto de Valores de Entrada; Conjunto de Valores de Sada;

X Funo de Entrada tal que: X: X V Y Funo de Sada tal que: Y : V Y F Conjunto de Interpretaes de Operaes tal que, para cada identificador de operao F interpretado por M, existe uma nica funo: F: V V em F T Conjunto de Interpretaes de Testes tal que, para cada identificador de teste T interpretado por M, existe uma nica funo: T: V {verdadeiro, falso} em T

EXEMPLO 2.7 Mquina de Dois Registradores.____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 21


Suponha uma especificao de uma mquina com dois registradores a e b os quais assumem valores em N, com duas operaes e um teste: subtrao de 1 em a, se a > 0; adio de 1 em b; teste se a zero. Os valores de entrada so armazenados em a (zerando b) e a sada retorna o valor de b.dois_reg = (N2, N, N, armazena_a, retorna_b, {subtrai_a, adiciona_b}, {a_zero})

N2, N, N - Conjuntos de Memria, Entrada e Sada armazena_a: N N2 tal que, n N, armazena_a(n) = (n, 0) retorna_b: N2 N tal que, (n, m) N2, retorna_b(n, m) = m subtrai_a: N2 N2 tal que, (n, m) N2,subtrai_a(n, m) = (n-1, m), se n 0; subtrai_a(n, m) = (0, m), se n = 0

adiciona_b: N2 N2 tal que, (n,m)N2, adiciona_b(n,m) =(n, m+1) a_zero: N2 {verdadeiro, falso} tal que, (n, m) N2,a_zero(n, m) = verdadeiro, se n = 0; a_zero(n, m) = falso, se n 0.

Afirma-se que P um programa para mquina M se cada identificador de teste e operao em P tiver uma correspondente funo de teste e operao em M, respectivamente.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Definio 2.8

Programa para uma Mquina.

Sejam M = (V, X, Y, X, Y, F, T) uma mquina P um programa onde PF e PT so os conjuntos de identificadores de operaes e de testes de P, respectivamente. P um Programa para a Mquina M se, e somente, se: para qualquer F PF, existe uma nica funo F:VV em F; para qualquer T PT, existe uma nica funo T: V {verdadeiro, falso} em T. EXEMPLO 2.8 Programas para a Mquina de Dois Registradores. Programa Iterativo itv_ba at a_zero faa (subtrai_a;adiciona_b)Figura 2.8 Programa iterativo para a mquina de dois registradores

Programa Recursivo rec_ba rec_ba R onde R def (se a_zero ento seno S;R), S def subtrai_a;adiciona_bFigura 2.9 Programa recursivo para a mquina de dois registradores



2.3 Computaes e Funes Computadas Ser visto como as definies de programas e mquinas caminham juntas para a definio de computao. Uma computao um histrico do funcionamento da mquina para o programa, considerando um valor inicial. Uma vez definida a noo de computao, pode-se inferir a natureza da funo computada, por um dado programa, em uma dada mquina.

2.3.1 Computao Uma computao de um programa monoltico em uma mquina um histrico das instrues executadas e o correspondente valor de memria. O histrico representado na forma de uma cadeia de pares onde: cada par reflete um estado da mquina para o programa, ou seja, a instruo a ser executada e o valor corrente da memria; a cadeia reflete uma seqncia de estados possveis a partir do estado inicial, ou seja, instruo (rtulo) inicial e valor de memria considerado.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Definio 2.9 Computao de Programa Monoltico em uma Mquina.

Sejam M = (V, X, Y, X, Y, F, T) uma mquina P = (I, r) um programa monoltico para M onde L o seu correspondente conjunto de rtulos.

Uma Computao do Programa Monoltico P na Mquina M uma cadeia (finita ou infinita) de pares de L V:onde (s0, v0) tal que s0 = r o rtulo inicial do programa P e v0 o valor inicial de memria para cada par (sk, vk) da cadeia, onde k {0, 1, 2, ...}, tem-se que (suponha que F um identificador de operao, T um identificador de teste e r', r" so rtulos de L): a) Operao. Se sk o rtulo de uma operao da forma:

(s0, v0)(s1, v1)(s2, v2)...

sk: faa F v_para r' ento (sk+1, vk+1) = (r', F(vk)) sk: faa v_para r' ento (sk+1, vk+1) = (r', vk)

b) Teste. Se sk o rtulo de um teste da forma:

sk: se T ento v_para r' seno v_para r"ento (sk+1, vk+1) = ( ? , vk) sk+1 = r' se T(vk) = verdadeiro; sk+1 = r" se T(vk) = falso. Uma Computao dita Finita se a cadeia que a define finita e dita Infinita se a cadeia que a define infinita. para um dado valor inicial de memria, a correspondente cadeia de computao nica, ou seja, a computao determinstica; um teste no altera o valor corrente da memria; em uma computao infinita, rtulo algum da cadeia final.



EXEMPLO 2.9 Computao Finita de Programa Monoltico na Mquina de Dois Registradores. programa monoltico mon_ba para a mquina dois_reg Programa Monoltico mon_ba 1: se a_zero ento v_para 9 seno v_para 2 2: faa subtrai_a v_para 3 3: faa adiciona_b v_para 1 Para o valor inicial de memria (3, 0), a computao finita :(1, (3, 0)) (2, (3, 0)) (3, (2, 0)) (1, (2, 1)) (2, (2, 1)) (3, (1, 1)) (1, (1, 2)) (2, (1, 2)) (3, (0, 2)) (1, (0, 3)) (9, (0, 3)) instruo inicial e valor de entrada armazenado em 1, como a 0, desviou para 2 em 2, subtraiu do registrador a e desviou para 3 em 3, adicionou no registrador b e desviou para 1 em 1, como a 0, desviou para 2 em 2, subtraiu do registrador a e desviou para 3 em 3, adicionou no registrador b e desviou para 1 em 1, como a 0, desviou para 2 em 2, subtraiu do registrador a e desviou para 3 em 3, adicionou no registrador b e desviou para 1 em 1, como a = 0, desviou para 9

EXEMPLO 2.10 Computao Infinita de Programa Monoltico na Mquina de Dois Registradores. programa monoltico comp_infinita para a mquina dois_reg. Programa Monoltico comp_infinita 1: faa adiciona_b v_para 1 Para o valor inicial de memria (3, 0), a computao infinita (1, (3, 0)) (1, (3, 1)) (1, (3, 2)) (1, (3, 3)) ... instruo inicial e valor de entrada armazenado adicionou no registrador b e permanece em 1 adicionou no registrador b e permanece em 1 adicionou no registrador b e permanece em 1 repete 1, adicionando no registrador b, indefinidamente


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

A computao de um programa recursivo em uma mquina anloga de um monoltico. O histrico representado na forma de uma cadeia de pares onde: cada par reflete um estado da mquina para o programa, ou seja, a expresso de sub-rotina a ser executada e o valor corrente da memria; a cadeia reflete uma seqncia de estados possveis a partir do estado inicial. A Computao dita Finita ou Infinita, se a cadeia que a define finita ou infinita, respectivamente. para um dado valor inicial de memria, a correspondente cadeia de computao nica, ou seja, a computao determinstica; um teste ou uma referncia a uma sub-rotina no alteram o valor corrente da memria; em uma computao finita, a expresso ocorre no ltimo par da cadeia e no ocorre em qualquer outro par; em uma computao infinita, expresso alguma da cadeia .



Definio 2.10 Computao de Programa Recursivo em uma Mquina. Sejam M = (V, X, Y, X, Y, F, T) uma mquina P um programa recursivo para M tal que: P E0 onde R1 def E1, R2 def E2,...,Rn def En Uma Computao do Programa Recursivo P na Mquina M uma cadeia de pares da forma: onde (D0, v0) tal que D0 = E0; e v0 o valor inicial de memria; para cada par (Dk, vk) da cadeia, onde k {0, 1, 2, ...}, tem-se que (suponha que F um identificador de operao, T um identificador de teste e C, C1, C2 so expresses de sub-rotina): Caso 1. Se Dk uma expresso de sub-rotina da forma: ento (Dk+1, vk+1) = (C, vk) Caso 2. Se Dk uma expresso de sub-rotina da forma: ento (Dk+1, vk+1) = (C, F(vk)) Caso 3. Se Dk uma expresso de sub-rotina da forma: ento (Dk+1, vk+1) = (Ei;C, vk) Caso 4. Se Dk uma expresso de sub-rotina da forma: ento (Dk+1, vk+1) = (C1;(C2;C), vk) Caso 5. Se Dk uma expresso de sub-rotina da forma:

(D0, v0) (D1, v1) (D2, v2)...

Dk = (;C) Dk = F;C Dk = Ri;C

Dk =(C1;C2);C

Dk = Ek = (se T ento C1 seno C2);C

ento (Dk+1, vk+1) = ( ? , vk ) Dk+1 = C1;C se T(vk) = verdadeiro Dk+1 = C2;C se T(vk) = falso


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

EXEMPLO 2.11 Computao Infinita de Programa Recursivo. programa recursivo qq_mquina um programa para qualquer mquina Programa Recursivo qq_mquina qq_mquina R onde R def R Para qualquer valor inicial de memria, a correspondente computao sempre infinita e a cadeia: (R, v0)(R, v0)(R, v0)... EXEMPLO 2.12 Computao Finita de Programa Recursivo na Mquina de Um Registrador. Para um dado conjunto A, a Funo Identidade em A aquela que associa, a cada elemento do conjunto, o prprio elemento, ou seja: idA: A A , tal que, para qualquer a A, tem-se que idA(a) = a. Considera a Mquina de um Registrador um_reg um_reg = (N, N, N, idN, idN, {ad, sub}, {zero}) N, N, N Conjuntos de Memria, Entrada e Sada idN: N N a funo identidade em N ad: N N tal que, n N, ad(n) = n+1 sub: N N tal que, n N, sub(n) = n-1 sub(n) = n-1, se n 0; sub(n) = 0, se n = 0 zero: N {verdadeiro, falso} tal que, n N, zero(n) = verdadeiro, se n = 0; zero(n) = falso, caso contrrio. Considere o programa recursivo duplica para a mquina um_reg .Programa Recursivo duplica duplica R onde R def (se zero ento seno sub;R;ad;ad)



Para o valor inicial de memria 3, a computao finita (R;, 3) valor de entrada armazenado ((se zero ento seno (sub;R;ad;ad));, 3) caso 3 ((sub;R;ad;ad);, 3) como n 0, executa seno (sub;(R;ad;ad);, 3) caso 4, composio seqencial ((R;ad;ad); , 2) subtraiu 1 da memria (R;(ad;ad);, 2) caso 4, composio seqencial ((se zero ento seno (sub;R;ad;ad));(ad;ad);, 2) caso 3 ((sub;R;ad;ad);(ad;ad);, 2) como n 0, executa seno (sub;(R;ad;ad);(ad;ad);, 2) caso 4, composio seqencial ((R;ad;ad);(ad;ad);, 1) subtraiu 1 da memria (R;(ad;ad);(ad;ad);, 1) caso 4, composio seqencial ((se zero ento seno(sub;R;ad;ad));(ad;ad);(ad;ad);, 1) caso 3 ((sub;R;ad;ad));(ad;ad);(ad;ad);, 1) como n 0, executa seno (sub;(R;ad;ad); (ad;ad);(ad;ad);, 1) caso 4, composio seqencial ((R;ad;ad);(ad;ad);(ad;ad);, 0) subtraiu 1 da memria (R;(ad;ad);(ad;ad);(ad;ad);, 0) caso 4, composio seqencial ((se zero ento seno (sub;R;ad;ad));(ad;ad);(ad;ad);(ad;ad);, 0) caso 3 (;(ad;ad);(ad;ad);(ad;ad);, 0) como n = 0, executa ento ((ad;ad);(ad;ad);(ad;ad);, 0) caso 1 (ad;(ad;(ad;ad);(ad;ad);), 0) caso 4, composio seqencial ((ad;(ad;ad);(ad;ad);), 1) adicionou 1 na memria (ad;((ad;ad);(ad;ad);), 1) caso 4, composio seqencial (((ad;ad);(ad;ad);), 2) adicionou 1 na memria (ad;(ad;(ad;ad);), 2) caso 4, composio seqencial ((ad;(ad;ad);), 3) adicionou 1 na memria (ad;((ad;ad);), 3) caso 4, composio seqencial (((ad;ad);), 4) adicionou 1 na memria (ad;((ad);), 4) caso 4, composio seqencial (((ad);), 5) adicionou 1 na memria (ad;(), 5) caso 4, composio seqencial ((), 6) adicionou 1 na memria (, 6) fim da recurso Figura 2.17 Computao finita na mquina de um registrador Note-se que o valor final na memria o valor inicial duplicado. Observe-se que, usando a noo de recurso, no foi necessrio usar duas clulas de memria, uma para controlar o ciclo e outra para calcular o resultado. A facilidade de recurso usada para determinar quantas vezes a operao ad necessita ser executada.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

2.3.2 Funo ComputadaA computao de um programa deve ser associada a uma entrada e a uma sada. Adicionalmente, espera-se que a resposta (sada) seja gerada em um tempo finito. Essas noes induzem a definio de funo computada. A funo computada por um programa monoltico sobre uma mquina: a computao inicia na instruo identificada pelo rtulo inicial, com a memria contendo o valor inicial resultante da aplicao da funo de entrada sobre o dado fornecido; executa, passo a passo, testes e operaes, na ordem determinada pelo programa, at atingir um rtulo final, quando pra; o valor da funo computada pelo programa o valor resultante da aplicao da funo de sada ao valor da memria quando da parada. Definio 2. 11 Funo Computada por um Programa Monoltico em uma Mquina. Sejam M = (V, X, Y, X, Y, F, T) uma mquina P um programa monoltico para M. A Funo Computada pelo Programa Monoltico P na Mquina M denotada por: uma funo parcial definida para x X se a cadeia: (s0, v0)(s1, v1)...(sn, vn) uma computao finita de P em M, onde o valor inicial da memria dado pela funo de entrada, ou seja, v0 = X(x). Neste caso, a imagem de x dada pela funo de sada aplicada ao ltimo valor da memria na computao, ou seja:

P, M: X Y

P, M(x) = Y(vn)



EXEMPLO 2.13 Funo Computada por Programa Monoltico na Mquina de Dois Registradores. Considere o programa monoltico mon_ba para a mquina dois_reg . A correspondente funo computada a funo identidade, mon_ba, dois_reg: N N tal que, para qualquer n N, tem-se que: mon_ba, dois_reg(n) = n Por exemplo, para o valor entrada de 3, tem-se que: X(3) = (3, 0); mon_ba, dois_reg(3) = Y(0, 3) = 3. Portanto, mon_ba, dois_reg definida para 3. EXEMPLO 2.14 Funo Computada por Programa Monoltico na Mquina de Dois Registradores. Considere o programa monoltico comp_infinita para a mquina dois_reg. A funo computada comp_infinita, dois_reg: N N, para a entrada de valor 3: X(3) = (3, 0); Como a cadeia infinita, a funo computada no definida para o valor de entrada 3.

A funo computada por um programa recursivo sobre uma mquina anloga de um monoltico: a computao inicia na expresso inicial com a memria contendo o valor inicial resultante da aplicao da funo de entrada sobre o dado fornecido; executa, passo a passo, testes e operaes, na ordem determinada pelo programa, at que a expresso de sub-rotina resultante seja a expresso vazia, quando pra; o valor da funo computada pelo programa o valor resultante da aplicao da funo de sada ao valor da memria quando da parada.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Definio 2.12 Funo Computada por um Programa Recursivo em uma Mquina. Sejam M = (V, X, Y, X, Y, F, T) uma mquina P um programa recursivo para M. A Funo Computada pelo Programa Recursivo P na Mquina M denotada por: uma funo parcial definida para x X se a seguinte cadeia uma computao finita de P em M: (D0, v0) (D1, v1)...(Dn, vn) onde: D0 = E0 expresso inicial de P v0 = X(x) En = Neste caso, tem-se que: P, M(x) = Y(vn) EXEMPLO 2.15 Funo Computada por Programa Recursivo. Considere o programa recursivo qq_mquina e uma mquina M = (V, X, Y, X, Y, F, T) qualquer. A correspondente funo computada : qq_mquina, M: X Y e indefinida para qualquer entrada. EXEMPLO 2.16 Funo Computada por Programa Recursivo na Mquina de Um Registrador. Considere o programa recursivo duplica para a mquina um_reg. A correspondente funo computada : duplica, um_reg: N N e tal que, para qualquer n N: duplica, um_reg(n) = 2n.

P, M: X Y



2.4 Equivalncias de Programas e Mquinas

2

1

3

Relao Equivalncia Forte de Programas. Um par de programas pertence relao se as correspondentes funes computadas coincidem para qualquer mquina; Relao Equivalncia de Programas em uma Mquina. Um par de programas pertence relao se as correspondentes funes computadas coincidem para uma dada mquina; Relao Equivalncia de Mquinas. Um par de mquina pertence relao se as mquinas podem se simular mutuamente. A simulao de uma mquina por outra pode ser feita usando programas diferentes. A Relao Equivalncia Forte de Programas especialmente importante pois, ao agrupar diferentes programas em classes de equivalncias de programas cujas funes coincidem, fornece subsdios para analisar propriedades de programas como complexidade estrutural. Um importante resultado que programas recursivos so mais gerais que os monolticos, os quais, por sua vez, so mais gerais que os iterativos. Igualdade de Funes Parciais. Duas funes parciais f, g: X Y so ditas iguais, ou seja, f = g, se, e somente se, para cada x X: ou f(x) e g(x) so indefinidas; ou ambas so definidas e f(x) = g(x). Composio Sucessiva de Funes. Para uma dada funo f: S S, a composio sucessiva de f com ela prpria denotada usando n expoente, f = f f... f (n vezes)


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

2.4.1 Equivalncia Forte de ProgramasDefinio 2.13 Relao Equivalncia Forte de Programas, Programas Equivalentes Fortemente. Sejam P e Q dois programas arbitrrios, no necessariamente do mesmo tipo. Ento o par (P, Q) est na Relao Equivalncia Forte de Programas, denotada por: P Q se, e somente se, para qualquer mquina M, as correspondentes funes parciais computadas so iguais, P, M = Q, M. Neste caso, P e Q so ditos Programas Equivalentes Fortemente. EXEMPLO 2.17 Programas Equivalentes Fortemente. Considere os quatro programas na figura abaixo. Os programas monolticos P1 e P2 , o iterativo P3 e o recursivo P4 so todos equivalentes fortemente.partida partida

T f parada

v

F

T f parada

v

F

Programa Monoltico P1

T f parada

v


Programa Iterativo P3 enquanto T faa (F) Programa Recursivo P4 P4 R onde R def (se T ento F;R seno )Figura 2.18 Quatro equivalncias forte de programas



Programa monolticopartida

Programa Monoltico P11:seTento v_para2 seno v_para3 2:faa F v_para 1

T f parada

v

F

conjunto de instrues rotuladas


Sejam M = (V, X, Y, X, Y, F, T) uma mquina arbitrria x X tal que X(x) = v. Se P1, M definida para x computao dada pela cadeia: (1, v) (2, v) (1, F(v)) (2, F(v)) (1, F2(v)) (2, F2(v)) ...(1, Fn(v)) (3, Fn(v)) supondo que n o menor natural tal que T(Fn(v)) = falso. Neste caso: P1, M(x) = Y(Fn(v))


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Programa Recursivo P4 P4 R onde R def (se T ento F;R seno ) Se P4, M definida para x, Computao dada por:(R, v) ((se T ento F;R seno ), v) (F;R, v) (R, F(v)) ((se T ento F;R seno ), F(v)) (F;R, F(v))

(R, F2(v)) ((se T ento F;R seno ), F2(v)) (F;R, F2(v)) ... (R, Fn(v)) ((se T ento F;R seno ), Fn(v)) (, Fn(v)) supondo que n o menor natural tal que T(Fn(v)) = falso. Neste caso: P4, M(x) = Y(Fn(v))

Portanto, P1 P4 pois, para qualquer mquina M, tem-se que: P1, M = P4, M



Relao Equivalncia Forte de Programas

permite identificar diferentes programas em uma mesma classe de equivalncia, ou seja, identificar diferentes programas cujas funes computadas coincidem, para qualquer mquina; as funes computadas por programas equivalentes fortemente tm a propriedade de que os mesmos testes e as mesmas operaes so efetuados na mesma ordem, independentemente do significado dos mesmos; fornece subsdios para analisar a complexidade estrutural de programas. Por exemplo, analisando os programas monolticos equivalentes fortemente P1 e P2 pode-se concluir que P1 estruturalmente "mais otimizado" que P2, pois contm um teste a menos.p a rtida p a rtida

T f p a ra da

v

F

T f p a ra da

v

F

P ro g ra m a M o n o ltic o P1

T f p a ra da

v

P ro g ra m a M o n o ltic o P2


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

para todo programa iterativo, existe um programa monoltico fortemente equivalente; para todo programa monoltico, existe um programa recursivo fortemente equivalente. Entretanto, a inversa no necessariamente verdadeira, ou seja, relativamente Relao Equivalncia Forte de Programas, programas recursivos so mais gerais que os monolticos, os quais, por sua vez, so mais gerais que os iterativos, induzindo uma hierarquia de classes de programas

Pr og ramas Progr amas Progr am as

Re cursiv o s Monolt icos It e rat iv os

Hierarquia induzida pela Relao Equivalncia Forte de Programas



Teorema 2.14 Equivalncia Forte de Programas: Monoltico. Iterativo

Para qualquer programa iterativo P , existe um programa monoltico P, tal que P P. Prova: Seja Pi um programa iterativo qualquer. Seja Pm um programa monoltico indutivamente construdo como segue: a) Para a operao vazia corresponde o fluxograma elementar: b) Para cada identificador de operao fluxograma elementar:FF

F

de

Pi

corresponde o seguinte

c) Composio Seqencial.

V;W d) Composio Condicional.

V

W

V

v

T

f

W

(se T ento V seno W) e) Composio Enquanto. enquanto T faa (V) f) Composio At. at T faa (V)v T f V

V

v

T

f


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Teorema 2.15 Equivalncia Forte de Programas:

Monoltico

Recursivo.

Para qualquer programa monoltico Pm, existe um programa recursivo Pr, tal que Pm Pr. Prova: Seja Pm um programa monoltico qualquer onde L = {r1, r2, ..., rn} o correspondente conjunto de rtulos. Suponha que, em Pm, rn o nico rtulo final. Ento Pr um programa recursivo construdo a partir de Pm e tal que: Pr R1 onde R1 def E1, R2 def E2, ...,Rn def para k {1, 2, ..., n-1}, Ek definido como segue:a)

Operao. Se rk da forma: rk: faa F v_para rk' ento Ek a seguinte expresso de sub-rotinas: F;Rk'

b) Teste. Se rk da forma: rk: se T ento v_para rk' seno v_para rk" ento Ek a seguinte expresso de sub-rotinas: (se T ento Rk' seno Rk") Corolrio 2.16 Equivalncia Forte de Programas: Iterativo Recursivo. Para qualquer programa iterativo Pi, existe um programa recursivo Pr, tal que Pi Pr. Teorema 217 Equivalncia Forte de Programas: Recursivo Monoltico. Dado um programa recursivo Pr qualquer, no necessariamente existe um programa monoltico Pm, tal que Pr Pm.



PROVA: (Por Absurdo). Para provar, suficiente apresentar um programa recursivo que, para uma determinada mquina, no apresente programa monoltico fortemente equivalente. Considere o programa recursivo duplica e a mquina um_reg. A funo computada duplica, um_reg: N N, para qualquer n N: duplica, um_reg(n) = 2n Suponha que existe um programa monoltico Pm que computa a mesma funo, ou seja, que Pm, um_reg: N N e: duplica, um_reg = Pm, um_reg Suponha que Pm constitudo de k operaes ad. Suponha n N tal que n k. Ento, para que Pm, um_reg (n) = 2n, necessrio que Pm execute n vezes a operao ad. Mas, como n k, ento pelo menos uma das ocorrncias de ad ser executada mais de uma vez, ou seja, existe um ciclo em Pm. Na funo computada por dois programas equivalentes fortemente, os mesmos testes e as mesmas operaes so efetuados na mesma ordem; portanto, o programa monoltico correspondente no pode intercalar testes de controle de fim de ciclo na seqncia de operaes ad (no programa recursivo, as operaes ad no so intercaladas por qualquer outra operao ou teste) . Portanto, a computao resultante infinita e a correspondente funo no definida para n, o que um absurdo, pois suposto que os dois programas so equivalentes fortemente. Logo, no existe um programa monoltico fortemente equivalente ao programa recursivo duplica.____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 42

1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

COMENTRIOS:Para melhor entender o esse resultado: um programa de qualquer tipo no pode ser modificado dinamicamente, durante uma computao; um programa, para ser fortemente equivalente a outro, no pode conter ou usar facilidades adicionais como memria auxiliar ou operaes ou testes extras; para que um programa monoltico possa simular uma recurso sem um nmero finito e predefinido de quantas vezes a recurso pode ocorrer, seriam necessrias infinitas opes de ocorrncias das diversas operaes ou testes envolvidos na recurso em questo; infinitas opes implicam um programa infinito, o que contradiz a definio de programa monoltico, o qual constitudo por um conjunto finito de instrues rotuladas.



Teorema 2.18 Equivalncia Forte de Programas: Iterativo. Monoltico

Dado um programa monoltico Pm qualquer, no necessariamente existe um programa iterativo Pi, tal que Pm Pi.PROVA: (Por Absurdo). Para provar, suficiente apresentar um programa monoltico que, para uma determinada mquina, no apresente programa iterativo fortemente equivalente. Considere o programa monoltico par e a mquina um_regpartida

ad

v

zero

f

sub

v

zero

f

sub

parada

a funo computada par, um_reg: N N tal que, para qualquer n N: par, um_reg(n) = 1, se n par; par, um_reg(n) = 0, se n mpar. Ou seja, retorna o valor 1 sempre que a entrada par, e zero, caso contrrio.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Suponha que existe um programa iterativo Pi que computa a mesma funo, ou seja, que Pi, um_reg: N N e: par, um_reg = Pi, um_reg Suponha que Pi constitudo de k operaes sub. n N tal que n k. Ento, necessrio que Pi execute n vezes a operao sub. Mas, como n k, ento pelo menos uma das ocorrncias de sub ser executada mais de uma vez, ou seja, existe um ciclo iterativo (do tipo enquanto ou at) em Pi. Em qualquer caso, o ciclo terminar sempre na mesma condio, independentemente se o valor for par ou mpar. Portanto, a computao resultante incapaz de distinguir entre os dois casos, o que um absurdo, pois suposto que os dois programas so equivalentes fortemente. Logo, no existe um programa iterativo fortemente equivalente ao programa monoltico par.

Observao 2.19: Poder Computacional dos Diversos Tipos de Programas.

Os teoremas acima podem dar a falsa impresso de que o poder computacional da classe dos programas recursivos maior que a dos monolticos que, por sua vez, maior que a dos iterativos. importante constatar que as trs classes de formalismos possuem o mesmo poder computacional, ou seja: para qualquer programa recursivo (respectivamente, monoltico) e para qualquer mquina, existe um programa monoltico (respectivamente, iterativo) e existe uma mquina tal que as correspondentes funes computadas coincidem. Para efeito de anlise de poder computacional, pode-se considerar mquinas distintas para programas distintos e no necessariamente existe uma relao entre as operaes e testes (e a ordem de execuo) dos programas.



2.4.2 Equivalncia de ProgramasDefinio 2.20 Relao Equiv de Programas em uma Mquina Uma noo de equivalncia mais fraca Sejam P e Q dois programas arbitrrios, no necessariamente do mesmo tipo e uma mquina M qualquer. Ento o par (P, Q) est na Relao Equivalncia de Programas na Mquina M, denotado por: P M Q se, e somente se, as correspondentes funes parciais computadas so iguais, ou seja: P, M = Q, M Neste caso, P e Q so ditos Programas Equivalentes na Mquina M, ou simplesmente Programas M-Equivalentes. Existem mquinas nas quais no se pode provar a existncia de um algoritmo para determinar se, dados dois programas, eles so ou no M-equivalentes.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

2.4.3 Equivalncia de MquinasDefinio 2.21 Simulao Forte de Mquinas Sejam M = (VM, X, Y, XM, YM, FM, TM) e N = (VN, X, Y, XN, YN, FN, TN) duas mquinas arbitrrias. N Simula Fortemente M se, e somente se, para qualquer programa P para M, existe um programa Q para N, tal que as correspondentes funes parciais computadas coincidem, ou seja: P, M = Q, N

importante observar que a igualdade de funes exige que os conjuntos de domnio e contra-domnio sejam iguais. Pode-se contornar essa dificuldade, tornando menos restritiva a definio de simulao, atravs da noo de codificaes.

Definio 2.22 Simulao de Mquinas Sejam M = (VM, XM, YM, XM, YM, FM, TM) e N = (VN, XN, YN, XN, YN, FN, TN) duas mquinas arbitrrias. N Simula M se, e somente se, para qualquer programa P para M, existe um programa Q para N e existem Funo de Codificao c: XM XN Funo de Decodificao d: YN YM tais que: P, M = d Q, N c Definio 2.23 Relao Equivalncia de Mquinas Sejam M e N duas mquinas arbitrrias. Ento o par (M, N) est na Relao Equivalncia de Mquinas, se, e somente se: M simula N e N simula M.



2.5 Verificao da Equivalncia Forte de Programas Mostra-se que existe um algoritmo para decidir a equivalncia forte entre programas monolticos. Como todo programa iterativo possui um programa monoltico equivalente fortemente, o mesmo pode ser afirmado para programas iterativos. A verificao de que dois programas monolticos so equivalentes fortemente usa os seguintes conceitos: a) Mquina de Traos. Produz um rastro ou histrico (denominado trao) da ocorrncia das operaes do programa. Neste contexto, dois programas so equivalentes fortemente se so equivalentes em qualquer mquina de traos. Programa Monoltico com Instrues Rotuladas Compostas. Instrues rotuladas compostas constituem uma forma alternativa de definir programas monolticos. Basicamente, uma instruo rotulada composta um teste da seguinte forma :

b)

r1: seT ento faa F v_para r2 seno faa G v_para r3

De fato, usando mquinas de traos, fcil verificar que, para um dado fluxograma, possvel construir um programa equivalente fortemente, usando instrues rotuladas compostas. Instrues rotuladas compostas induzem a noo de rtulos equivalentes fortemente, a qual usada para determinar se dois programas so ou no equivalentes fortemente.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

2.5.1 Mquina de Traos Uma mquina de traos no executa as operaes propriamente ditas, mas apenas produz um histrico ou rastro da ocorrncia destas, denominado de trao. Essas mquinas so de grande importncia para o estudo da equivalncia de programas pois, se dois programas so equivalentes em qualquer mquina de traos, ento so equivalentes fortemente. Definio 2.24 Mquina de Traos. Uma Mquina de traos uma mquina onde: Op*conjunto de palavras de operaes onde Op = {F, G, ...} o qual corresponde, simultaneamente, aos conjuntos de valores de memria, de entrada e de sada; idOp*funo identidade em Op*, a qual corresponde, simultaneamente, s funes de entrada e sada; F conjunto de interpretaes de operaes onde, para cada identificador de operao F de Op, a interpretao F: Op* Op* tal que, para qualquer w Op*, F(w) resulta na concatenao do identificador F direita de w, ou seja: F(w) = wF T conjunto de interpretaes de testes, tal que, para cada identificador de teste T: T: Op* {verdadeiro, falso} funo de T efeito de cada operao interpretada por uma mquina de traos simplesmente o de acrescentar o identificador da operao direita do valor atual da memria. a funo computada consiste em um histrico das operaes executadas durante a computao. M = (Op*, Op*, Op*, idOp*, idOp*, F, T)



Definio 2.25 Funo Induzida por um Trao em uma Mquina Sejam M = (V, X, Y, X, Y, F, T) uma mquina,Op = {F, G, H, ...} o conjunto de operaes interpretadas em F e

w = FG...H um trao possvel de M, ou seja, w Op*. A Funo Induzida pelo Trao w na Mquina M, denotada por: [w, M]: X V a funo (total): [w, M] = H ... G F X A funo [w, M] aplicada a uma entrada x X denotada por: [wx, M] = H ... G F X(x) Portanto, a funo induzida por um trao nada mais do que a funo resultante da composio das interpretaes das diversas operaes que constituem o trao.

Teorema 2.26 Equivalncia Forte de Programas Equivalncia de Programas em Mquinas de Traos Sejam P e Q dois programas arbitrrios, no necessariamente do mesmo tipo. Ento: P Q se, e somente se, para qualquer mquina de traos M, P M Q. Corolrio 2.27 Equivalncia Forte de Programas Equivalncia de Programas em Mquinas de Traos. Sejam P e Q dois programas arbitrrios, no necessariamente do mesmo tipo. Ento: P Q se, e somente se, para qualquer mquina de traos M, P, M() = Q, M().


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

2.5.2 Instrues Rotuladas Compostas Instrues rotuladas compostas possuem somente um formato, ao contrrio das instrues rotuladas, as quais podem ter dois formatos: de operao e de teste. Definio 2.28 Instruo Rotulada Composta. Uma Instruo Rotulada Composta uma seqncia de smbolos da seguinte forma (suponha que F e G so identificadores de operao e que T um identificador de teste): r1: se T ento faa F v_para r2 seno faa G v_para r3 r2 e r3 so ditos rtulos sucessores de r1; r1 dito rtulo antecessor de r2 e r3. Definio 2.29 Programa Monoltico com Instrues Rotuladas Compostas Um Programa Monoltico com Instrues Rotuladas Compostas P um par ordenado P = (I, r) onde: I Conjunto de Instrues Rotuladas Compostas, o qual finito; r Rtulo Inicial o qual distingue a instruo rotulada inicial em I. Adicionalmente, relativamente ao conjunto I, tem-se que: no existem duas instrues diferentes com um mesmo rtulo; um rtulo referenciado por alguma instruo o qual no associado a qualquer instruo rotulada dito um Rtulo Final. Para simplificar o entendimento da determinao da equivalncia forte de programas monolticos, considerado somente o caso particular em que os programas possuem um nico identificador de teste, denotado por T. Considerando-se um nico identificador de teste, uma instruo rotulada composta da forma: r1:se T ento faa F v_para r2 seno faa G v_para r3 pode ser abreviada simplesmente por: r1: (F, r2), (G, r3)____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 51


Definio 2.30 Algoritmo Fluxograma Rotuladas Compostas. Ns - componentes elementares de partida, parada e operao de um fluxograma algoritmo para traduzir um fluxograma P para um programa monoltico P' constitudo por instrues rotuladas compostas: a) Rotulao de Ns. Rotula-se cada n do fluxograma. Suponha que existe um nico componente elementar de parada, ao qual associado o identificador (palavra vazia). O rtulo correspondente ao n partida o Rtulo Inicial do programa P'. b) Instrues Rotuladas Compostas. A construo de uma instruo rotulada composta parte do n partida e segue o caminho do fluxograma. b.1) Teste. Para um teste, a correspondente instruo rotulada composta : r1: (F, r2), (G, r3) b.2) Operao. Para uma operao, a correspondente instruo rotulada composta : r1: (F, r2), (F, r2) b.3) Parada. Para uma parada, a correspondente instruo rotulada composta como segue: r: (parada, ), (parada, ) b.4) Testes Encadeados. No caso de testes encadeados, segue-se o fluxo at que seja encontrado um n, resultando na seguinte instruo rotulada composta: r1: (F, r2), (G, r3) b.5) Testes Encadeados em Ciclo Infinito. Para um ciclo infinito determinado por testes encadeados, a correspondente instruo rotulada composta : r1: (F, r2), (ciclo, ) Neste caso, deve ser includa, adicionalmente, uma instruo rotulada composta correspondente ao ciclo infinito: : (ciclo, ), (ciclo, )


1

INTRODUO

Er1

CONCEITOS

BSICOS

________________________________________________________________________________________

Teste

r2

F

v

T

f

G

r3

r1 r1 r2F

Testes Encadeados

Operao

r2

F

v

T f

r r4 H

v

T

f

G

r3

parada

Parada

r1

r2

F

v

T f f

Testes Encadeados em Ciclos Infinitos

T

Figura 2.23 Instrues rotuladas compostasRotuladas Compostas. EXEMPLO 2.18 Algoritmo Fluxograma Considere o programa monoltico especificado na forma de fluxograma cujos ns j esto rotulados:____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 53


1

partida

2

G

v

T

f

F

3

4

F

v

T

f

G

5

6

F

v

T

f

G

f

T

v

v

T

f

7 parada

correspondente programa com instrues rotuladas compostas representado abaixo supondo que 1 o rtulo inicial.1: 2: 3: 4: 5: 6: 7: : (G, 2), (F, 3) (G, 2), (F, 3) (F, 4), (G, 5) (F, 4), (G, 5) (F, 6), (ciclo, ) (parada, ), (G, 7) (G, 7), (G, 7) (ciclo, ), (ciclo, )

Note-se que: o rtulo 2 sucessor dele mesmo. O mesmo ocorre com os rtulos 4, 7 e ; existem dois caminhos no fluxograma que atingem o n parada. S um representado no conjunto de instrues rotuladas compostas. na instruo rotulada por 7, ocorre um ciclo infinito.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

2.5.3 Equivalncia Forte de Programas Monolticos A unio disjunta de conjuntos garante que todos os elementos dos conjuntos componentes constituem o conjunto resultante, mesmo que possuam a mesma identificao. considera-se que os elementos so distintos, mesmo que possuam a mesma identificao. Exemplo: para os conjuntos A = {a, x} e B = {b, x}, o conjunto resultante da unio disjunta : {aA, xA, bB, xB} = {a, xA, b, xB} Corolrio 2.32 Equivalncia Forte: Unio Disjunta. Sejam: Q = (IQ, q) e R = (IR, r) dois programa monolticos especificados usando instrues rotuladas compostas Pq = (I, q) e Pr = (I, r) programas monolticos onde I o conjunto resultante da unio disjunta de IQ e IR. Ento: Pq Pr se, e somente se, Q R O algoritmo para verificao da equivalncia forte de Q e R resumese verificao se Pq e Pr so equivalentes fortemente. cadeia de conjunto: seqncia de conjuntos ordenada pela relao de incluso; programa monoltico simplificado: instrues rotuladas compostas que determinam ciclos infinitos so excludas (excetuando-se a instruo rotulada por , se existir). A simplificao baseia-se em cadeia de conjuntos; rtulos equivalentes fortemente: o algoritmo de verificao se Pq e Pr so equivalentes fortemente baseia-se em rtulos equivalentes fortemente de programas simplificados.



Definio 2.33 Cadeia de Conjuntos, Cadeia Finita de Conjuntos, Limite de uma Cadeia Finita de Conjuntos. Uma seqncia de conjuntos A0A1... dita: a) uma Cadeia de Conjuntos se, para qualquer k 0: Ak Ak+1 b) uma Cadeia Finita de Conjuntos uma cadeia de conjuntos onde existe n, para todo k 0, tal que: An = An+k c) o Limite da Cadeia Finita de Conjuntos : lim Ak = An Lema 2.34 Identificao de Ciclos Infinitos em Programa Monoltico. lema fornece um algoritmo para determinar se existem ciclos infinitos em um conjunto de instrues rotuladas compostas. A idia bsica partir da instruo parada, rotulada por , determinando os seus antecessores. Por excluso, um instruo que no antecessor da parada determina um ciclo infinito. Seja I um conjunto de n instrues rotuladas compostas. Seja A0A1... uma seqncia de conjuntos de rtulos indutivamente definida como segue: A0 = {} Ak+1 = Ak {r r rtulo de instruo antecessora de alguma instruo rotulada por Ak} Ento A0A1... uma cadeia finita de conjuntos, e, para qualquer rtulo r de instruo de I, tem-se que (I, r) (I, ) se, e somente se, r lim Ak O Lema acima proporciona uma maneira fcil de determinar se algum rtulo caracteriza ciclos infinitos.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

EXEMPLO 2.19 Identificao de Ciclos Infinitos em Programa Monoltico. Considere o conjunto I de instrues rotuladas compostas representado na Figura abaixo1: 2: 3: 4: 5: 6: 7: : (G, 2), (F, 3) (G, 2), (F, 3) (F, 4), (G, 5) (F, 4), (G, 5) (F, 6), (ciclo, ) (parada, ), (G, 7) (G, 7), (G, 7) (ciclo, ), (ciclo, )

A correspondente cadeia finita de conjuntos : A0 = {} A1 = {6, } A2 = {5, 6, } A3 = {3, 4, 5, 6, } A4 = {1, 2, 3, 4, 5, 6, } A5 = {1, 2, 3, 4, 5, 6, } Logo: lim Ak = {1, 2, 3, 4, 5, 6, } Simplificao de ciclos infinitos: (I, 7) (I, ), pois 7 lim Ak .

Portanto, pode-se simplificar um conjunto de instrues rotuladas compostas eliminando-se qualquer instruo de rtulo r que determine um ciclo infinito.



Definio 2.35 Algoritmo de Simplificao de Ciclos Infinitos. Seja I um conjunto finito de instrues rotulas compostas. O Algoritmo de Simplificao de Ciclos Infinitos : a) determina-se a correspondente cadeia finita de conjuntos A0A1... como no lema 2.34; b) para qualquer rtulo r de instruo de I tal que r lim Ak, tem-se que: a instruo rotulada por r excluda; toda referncia a pares da forma (F, r) em I substituda por (ciclo, ); I = I {: (ciclo, ), (ciclo, )}. EXEMPLO 2.20:. 1: 2: 3: 4: 5: 6: : (G, 2), (F, 3) (G, 2), (F, 3) (F, 4), (G, 5) (F, 4), (G, 5) (F, 6), (ciclo, ) (parada, ), (ciclo, ) (ciclo, ), (ciclo, )

Lema 2.36 Rtulos Consistentes. Seja I um conjunto finito de instrues rotuladas compostas e simplificadas. Sejam r e s dois rtulos de instrues de I, ambos diferentes de . Suponha que as instrues rotuladas por r e s so da seguinte forma, respectivamente: r: (F1, r1), (F2, r2) s: (G1, s1), (G2, s2) Ento: r e s so consistentes se, e somente se, F1 = G1 e F2 = G2


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Definio 2.37 Rtulos Equivalentes Fortemente. Seja I um conjunto finito de instrues rotuladas compostas e simplificadas. Sejam r e s dois rtulos de instrues de I. Suponha que as instrues rotuladas por r e s so da seguinte forma, respectivamente: r: (F1, r1), (F2, r2) s: (G1, s1), (G2, s2) Ento, r e s so Rtulos Equivalentes Fortemente se, e somente se: ou r = s = ; ou r e s so ambos diferentes de e consistentes, ou seja F1 = G1 e F2 = G2 Teorema 2.38 Determinao de Rtulos Equivalentes Fortemente. Seja I um conjunto de n instrues compostas e simplificadas. Sejam r e s dois rtulos de instrues de I. Define-se, indutivamente, a seqncia de conjuntos B0B1... por: B0 = {(r, s)} Bk+1 = {(r", s")r" e s"so rtulos sucessores de r e s, respectivamente, (r, s) Bk e (r", s") Bi , (0 i k)} Ento B0B1... uma seqncia que converge para o conjunto vazio, e r, s so rtulos equivalentes fortemente se, e somente se, qualquer par de Bk constitudo por rtulos consistentes.



Definio 2.39Algoritmo de Verificao da Equivalncia Forte de Programas Monolticos.

Sejam Q = (IQ, q) e R = (IR, r) dois programas monolticos especificados usando instrues rotuladas compostas e simplificado. Algoritmo de Verificao da Equivalncia Forte de Programas Monolticos Q e R determinado pelos passos: Passo 1. Sejam Pq = (I, q) e Pr = (I, r) programas monolticos onde I o conjunto resultante da unio disjunta de IQ e IR, excetuando-se a instruo rotulada , se existir, a qual ocorre, no mximo, uma vez em I. Passo 2. Se q e r so rtulos equivalentes fortemente, ento B0={(q, r)}. Caso contrrio, Q e R no so equivalentes fortemente, e o algoritmo termina. Passo 3. Para k 0, define-se o conjunto Bk+1, contendo somente os pares (q", r") de rtulos sucessores de cada (q', r') Bk, tais que: q' r'; q' e r' so ambos diferentes de ; os pares sucessores (q", r") no so elementos de B0, B1, ... , Bk. Passo 4. Dependendo de Bk+1, tem-se que: a) Bk+1 = : Q e R so equivalentes fortemente, e o algoritmo termina; b) Bk+1 : se todos os pares de rtulos de Bk+1 so equivalentes fortemente, ento v para o Passo 3; caso contrrio, Q e R no so equivalentes fortemente, e o algoritmo termina.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

EXEMPLO 2.21 Algoritmo de Verificao da Equivalncia Forte de Programas Monolticos. Considere os programas monolticos especificados na forma de fluxograma Q (Exemplo 2.18 Figura 2.25) e R (dado abaixo):8partida

9

G

v

T

f

F

10

v

T

f

G

11

12

F

v

T

f

F

13

f

T

v

parada

Figura 2.27 - Programa Monoltico R a) 1: 2: 3: 4: 5: 6: : A especificao do programa Q usando instrues rotuladas compostas, j simplificado, j foi feita na Figura 2.26. (G, 2), (F, 3) (G, 2), (F, 3) (F, 4), (G, 5) (F, 4), (G, 5) (F, 6), (ciclo, ) (parada, ), (ciclo, ) (ciclo, ), (ciclo, )



b) Em relao ao programa R, tem-se que: b.1) Conjunto de instrues rotuladas compostas. 8: 9: 10: 11: 12: 13: (G, 9), (F, 10) (G, 9), (F, 10) (F, 10), (G, 11) (F, 12), (F, 13) (parada, ), (F, 13) (F, 13), (F, 13)

b.2) Identificao de ciclos infinitos. A0 = {} A1 = {12, } A2 = {11, 12, } A3 = {10, 11, 12, } A4 = {8, 9, 10, 11, 12, } A5 = {8, 9, 10, 11, 12, } Portanto: lim Ak = {8, 9, 10, 11, 12, } (IR, 13) (I, ), pois 13 lim Ak. b.3) Simplificao de ciclos infinitos. 8: 9: 10: 11: 12: : (G, 9), (F, 10) (G, 9), (F, 10) (F, 10), (G, 11) (F, 12), (ciclo, ) (parada, ), (ciclo, ) (ciclo, ), (ciclo, )


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

c)

Relativamente aplicao do algoritmo, tem-se que:

Passo 1. Seja I a unio disjunta dos conjuntos IQ e IR, excetuando-se a instruo rotulada , como segue: 1: (G, 2), (F, 3) 2: (G, 2), (F, 3) 3: (F, 4), (G, 5) 4: (F, 4), (G, 5) 5: (F, 6), (ciclo, ) 6: (parada, ), (ciclo, ) 8: (G, 9), (F, 10) 9: (G, 9), (F, 10) 10:(F, 10), (G, 11) 11:(F, 12), (ciclo, ) 12:(parada, ), (ciclo, ) : (ciclo, ), (ciclo, )

Para verificar se Q R, suficiente verificar se (I, 1) (I, 8).Passo 2. Como 1 e 8 so rtulos equivalentes fortemente, ento: B0 = {(1, 8)} Passos 3 e 4. Para k 0, construo de Bk+1 como segue: B1 = {(2, 9), (3, 10)} pares de rtulos equivalentes fortemente B2 = {(4, 10), (5, 11)} pares de rtulos equivalentes fortemente B3 = {(6, 12), (, )} pares de rtulos equivalentes fortemente pares de rtulos equivalentes fortemente B4 = {(, )} B5 = Logo (I, 1) (I, 8), e, portanto, Q R.



EXEMPLO 2.22 Algoritmo de Verificao da Equivalncia Forte deProgramas Monolticos.

Os programas monolticos (fluxogramas) reproduzidos na Figura 2.28 com os ns rotulados so equivalentes fortemente.partida partida

1 2

3

T f parada

v

F

T f parada

v

F

4


T f parada

v


a)

Figura 2.28 Fluxogramas P1 e P2 equivalentes fortemente A especificao do programa P1 usando instrues rotuladas compostas (e j simplificadas) : 1: (F, 2), (parada, ) 2: (F, 2), (parada, )

b)

A especificao de P2 usando instrues rotuladas compostas (e j simplificadas) : 3: (F, 4), (parada, ) 4: (F, 4), (parada, )

os correspondentes conjuntos de instrues rotuladas compostas so iguais, a menos dos rtulos. aplicao do algoritmo: fcil verificar que (I, 1) (I, 3). a relao equivalncia forte fornece subsdios para analisar a complexidade estrutural de programas. No caso, P1 estruturalmente mais otimizado que P2.____________________________________________________________ Teoria da Computao - Profs. Tiaraju Diverio e Paulo Blauth Menezes 64

1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

2.6 ConclusoForam introduzidos os conceitos de programa e de mquina, os quais so usados para construir as definies de computao e de funo computada. foram estudados trs tipos de programas: monoltico, iterativo e recursivo. Os recursivos so mais gerais que os monolticos os quais, por sua vez, so mais gerais que os iterativos. Apresentaram-se as noes de equivalncia de programas e de mquinas Mostrou-se a existncia de um algoritmo para verificar se programas monolticos (ou iterativos) so fortemente equivalentes.

Programas

Mquinas

Computaes

Funes Computadas

Programas Equivalentes

Mquinas Equivalentes

Funes Computveis

Mquina Universal

Figura 2.29 Relao entre os conceitos



3 Mquinas Universais3.1 Codificao de Conjuntos Estruturados 3.2 Mquina de Registradores - Norma 3.3 Mquina Norma como Mquina Universal3.3.1 Operaes e Testes 3.3.2 Valores Numricos 3.3.3 Dados Estruturados 3.3.4 Endereamento Indireto e Recurso 3.3.5 Cadeias de Caracteres

3.4 Mquina de Turing3.4.1 Noo Intuitiva 3.4.2 Noo como Mquina 3.4.3 Modelo Formal 3.4.4 Mquinas de Turing como Reconhecedores de Linguagens 3.4.5 Mquinas de Turing como Processadores de Funes 3.4.6 Equivalncia entre as Mquinas de Turing e Norma

3.5 Outros Modelos de Mquinas Universais3.5.1 Mquina de Post 3.5.2 Mquina com Pilhas 3.5.3 Autmato com Duas Pilhas

3.6 Modificaes sobre as Mquinas Universais3.6.1 No-Determinismo 3.6.2 Mquina de Turing com Fita Infinita Esquerda e Direita 3.6.3 Mquina de Turing com Mltiplas Fitas 3.6.4 Outras Modificaes sobre a Mquina de Turing

3.7 Hierarquia de Classes de Mquinas 3.8 Hiptese de Church


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

3 MQUINAS UNIVERSAISAlgoritmo termo intuitivamente usado como soluo de um problema, como uma forma de descrever se determinada propriedade verificada ou no para uma dada classe de entrada.

Investigao da solucionabilidade de um problema Noo intuitiva de algoritmo

a investigao da existncia de um algoritmo capaz de resolv-lo. sua descrio deve ser finita e no-ambgua; deve consistir de passos discretos, executveis mecanicamente e em um tempo finito. Limitaes de tempo ou de espao podem determinar se um algoritmo pode ou no ser descrito na prtica. (no so restries tericas). estudo ser restrito aos algoritmos naturais, ou seja, definidos sobre o conjunto dos nmeros naturais.

qualquer conjunto contvel pode ser equivalente ao dos naturais, atravs de uma codificao. conceito de programa, como introduzido anteriormente, satisfaz noo intuitiva de algoritmo. Entretanto, necessrio definir a mquina a ser considerada.

Mquina

simples, para permitir estudos de propriedades, sem a necessidade de considerar caractersticas no-relevantes, bem como permitir estabelecer concluses gerais sobre a classe de funes computveis; poderosa, capaz de simular qualquer caracterstica de mquinas reais ou tericas, de tal forma que os resultados provados sejam vlidos para modelos aparentemente com mais recursos.



Mquina UniversalSe for possvel representar qualquer algoritmo como um programa em tal mquina, ento esta denominada de mquina universal. As evidncias de que uma mquina universal: Evidncia Interna. Consiste na demonstrao de que qualquer extenso das capacidades da mquina universal proposta computa, no mximo, a mesma classe de funes, ou seja, no aumenta o seu poder computacional; Evidncia Externa. Consiste no exame de outros modelos que definem a noo de algoritmo, juntamente com a prova de que so, no mximo, computacionalmente equivalentes.

Mquina Norma, uma mquina universal

um conjunto de registradores naturais trs instrues sobre os registradores: operao de incrementar um - sucessor operao de decrementar um - antecessor teste se o valor armazenado zero.

Mquina de Turing, proposta em 1936 por Alan Turing modelo mais utilizado como formalizao de algoritmo um mecanismo simples que formaliza a idia de uma pessoa que realiza clculos usando um instrumento de escrita e um apagador modelo formal baseado em uma fita (usada para entrada, sada e rascunho), uma unidade de controle um programa Na realidade, no se trata de uma mquina no sentido dado a essa palavra, mas sim de um programa para uma mquina universal.


1

INTRODUO

E

CONCEITOS

BSICOS

________________________________________________________________________________________

Hiptese de Church, apresentada em 1936 por Alonzo Church

afirma que qualquer funo computvel pode ser processada por uma Mquina de Turing, que existe um algoritmo expresso na forma de Mquina de Turing capaz de processar a funo. Como a noo intuitiva de algoritmo no matematicamente precisa, impossvel formalizar uma demonstrao de que a Mquina de Turing , efetivamente, o mais genrico dispositivo de computao. Entretanto, todas as evidncias internas e externas imaginadas foram sempre verificadas, reforando a Hiptese de Church. Os demais modelos de mquinas propostos, bem como qualquer extenso de suas capacidades, possuem, no mximo, a mesma capacidade computacional da Mquina Turing. Mquina de Post. Baseada na estrutura de dados do tipo fila (o primeiro dado armazenado o primeiro a ser recuperado); Autmato com Pilhas. Baseada na estrutura de dados do tipo pilha (o ltimo dado armazenado o primeiro a ser recuperado), onde so necessrias pelo menos duas pilhas para simular o mesmo poder computacional de uma fita ou fila. Extenses da Mquina de Turing no aumentam o seu poder computacional No-Determinismo. Permite que a mquina possa tentar diversos caminhos alternativos para uma mesma situao; Mltiplas fitas. Mais de uma fita. Mltiplas cabeas Fita infinita de ambos os lados



Uso de Mquinas de Turing Existem trs maneiras de abordar o estudo das Mquinas de Turinga) b)

Processarpropriedades;

Funes. Funes computveis e suas

Reconhecer Linguagens. Linguagens que podem serreconhecidas e suas propriedades;

c)

Solucionar Problemas. Problemas solucionveis e nosolucionveis, (computveis) computveis). problemas parcialmente solucionveis e completamente insolveis (no

As trs abordagens so usadas ao longo deste livro. A terceira constitui um dos problemas fundamentais da Cincia da Computao e tratada em

Documents

TeoriaCaomputacao e Book