Teoria da Computação(COM10395)
Profa. Juliana Pinheiro CamposE-mail: [email protected]
Ciência da Computação
TEORIA DA COMPUTAÇÃO
ProgramasUm programa é um conjunto estruturado de
instruções que capacitam uma máquina a aplicar sucessivamente certas operações básicas e testes sobre os dados iniciais fornecidos, com o objetivo de transformar estes dados numa forma desejável.
Um programa deve possuir uma estrutura de controle que explicita como as operações e testes devem ser compostos. Classificação das estruturas:
TEORIA DA COMPUTAÇÃO
Programas
Monolítica: baseada em desvios condicionais e incondicionais, não possuindo mecanismos explícitos de iteração ou recursão.
Iterativa: possui mecanismos de controle de iterações de trechos de programas. Não permite desvios incondicionais.
Recursiva: possui mecanismos de estruturação em sub-rotinas recursivas. Também não permite desvios incondicionais.
TEORIA DA COMPUTAÇÃO
Programas
Para o estudo de programas não é necessário saber qual a natureza precisa das operações e dos testes. Eles são identificados por nomes.
Identificadores de operações:
F, F1,F2, ... G, G1,G2, ... H, H1,H2,...
Identificadores de testes:
T, T1,T2, T3, ...
Operação vazia (que não faz nada): ν
TEORIA DA COMPUTAÇÃO
Programas monolíticos
Baseados em desvios condicionais e incondicionais.
A lógica é distribuída por todo o bloco (monólito) que constitui o programa.
A especificação de programas monolíticos pode ser feita por meio de fluxogramas ou instruções rotuladas.
TEORIA DA COMPUTAÇÃO
Programas monolíticos
Exemplo de especificação usando fluxogramas
FV
TEORIA DA COMPUTAÇÃO
Programas monolíticos
Uma instrução rotulada pode ser:• Operação:operação a ser executada seguida de um
desvio incondicional para a instrução subsequente.
• Teste: determina um desvio condicional.
Exemplo de especificação usando instruções rotuladas
1: faça F e vá para 22: se T1 então vá para 1 senão vá para 33: faça G e vá para 44: se T2 então vá para 5 senão vá para 1
Uma parada é especificada usando um desvio incondicional para um rótulo sem instrução correspondente.
TEORIA DA COMPUTAÇÃO
Programas monolíticos
Definição formal: um programa monolítico P é um par ordenado: P = (I, r) onde
• I é um conj. finito de instruções rotuladas (não existem 2 instruções diferentes com mesmo rótulo).
• r é o rótulo inicial que identifica a instrução inicial em I• um rótulo é dito final se é referenciado por pelo menos
uma instrução de I, mas não rotula nenhuma instrução de I.
Ex: P = (I1, 1) onde I1 é o conjunto constituído pelas instruções rotuladas 1, 2, 3 e 4 apresentadas anteriormente.
TEORIA DA COMPUTAÇÃO
Programas monolíticos
Ex: P = ({r1: faça v e vá para r2 }, r1).
Qual o fluxograma correspondente?
TEORIA DA COMPUTAÇÃO
Programas iterativos
Surgiram para solucionar problemas decorrentes da dificuldade de entendimento e manutenção de programas monolíticos.
Substitui desvios incondicionais por estruturas de controle de ciclos ou repetições resultando em melhor estruturação dos desvios.
Essas noções deram origem ao que hoje é chamado de programação estruturada.
TEORIA DA COMPUTAÇÃO
Programas iterativosSão baseados em 3 mecanismos de composição
(sequenciais) de programas:• Sequencial: composição de 2 programas, cujo efeito é a
execução do primeiro e após, a execução do segundo programa componente.
• Condicional: composição de 2 programas, cujo efeito é a execução de somente um dos 2 dependendo do resultado de um teste.
• Repetição: composição de 1 programa, cujo efeito é a execução, repetidamente, do programa componente enquanto o resultado de um teste for verdadeiro (enquanto) ou enquanto o resultado de um teste for falso (até).
TEORIA DA COMPUTAÇÃO
Programas iterativosDefinição Formal: Um programa iterativo P é
indutivamente definido como segue:
OBS: Considere V e W programas iterativos e T um
identificador de teste):
• A operação vazia ν é um programa iterativo
• Cada identificador de operação é um programa iterativo
• Composição seqüencial: V; W resulta em um programa iterativo cujo efeito é a execução de V e, após, a execução de W.
• Composição condicional: (se T então V senão W) resulta em um programa iterativo cujo efeito é a execução de V se T é verdadeiro ou W se T é falso.
TEORIA DA COMPUTAÇÃO
Programas iterativosDefinição Formal: Um programa iterativo P é
indutivamente definido como segue:• Composição enquanto: enquanto T faça (V) resulta em
um programa iterativo que testa T e executa V repetidamente enquanto o resultado do teste for verdadeiro.
• Composição até: até T faça (V) resulta em um programa iterativo que testa T e executa V, repetidamente, até que o resultado do teste for o valor verdadeiro.
Enquanto e até podem ser simulados por um fluxograma que
utiliza as componentes do fluxograma do programa
monolítico.
TEORIA DA COMPUTAÇÃO
Programas iterativos
Exemplo:
(se T1então enquanto T2
faça (até T3faça (V;W))
senão ν)
Operação vazia
TEORIA DA COMPUTAÇÃO
Programas recursivos
Admite a definição de sub-rotinas recursivas.Suponha um conjunto de identificadores de sub-
rotinas: R, R1, R2, R3, ...Cada sub-rotina é definida por uma expressão de
sub-rotinas, E, indutivamente definida como:
OBS: Considere D1 e D2 expressões de sub-rotinas e T um identificador de teste:
• A operação vazia ν é uma expressão de sub-rotina
TEORIA DA COMPUTAÇÃO
Programas recursivos
• Cada identificador de sub-rotina é uma expressão de sub-rotina
• Composição seqüencial: (D1; D2) resulta em uma expressão de sub-rotinas cujo efeito é a execução de D1 e, após, a execução de D2;
• Composição condicional: (se T então D1 senão D2) resulta em uma expressão de sub-rotinas cujo efeito é a execução de D1 se T é verdadeiro ou D2 se T é falso.
TEORIA DA COMPUTAÇÃO
Programas recursivos
Definição formal: Um programa recursivo P tem a seguinte forma:
P é E0 onde R1 def E1, R2 def E2, ..., Rn def Em
onde (suponha K pertencente a {1,2, ... n}):• E0 é a expressão inicial a qual é uma expressão
de sub-rotinas• Ek Expressão que define Rk, ou seja, a
expressão que define a sub-rotina identificada por Rk.
faça (V;W))
senão ν)
TEORIA DA COMPUTAÇÃO
Programas recursivos
Exemplo
P é R;Z onde R def F; (se T então R senão G; S),S def (se T então ν senão F; R),Z def (se T então G senão F)
Avalia-se a expressão inicial onde cada identificador de sub-rotina referenciado é substituído pela correspondente expressão que o define e assim sucessivamente até que seja substituído pela expressão vazia, que determina o fim da recursão.
TEORIA DA COMPUTAÇÃO
Máquinas
Um programa é uma sequencia de caracteres sem significado semântico.
A natureza das operações e dos testes é especificada na definição de máquina, a qual permite dar uma interpretação semântica do programa.
O objetivo de uma máquina é suprir todas as informações necessárias para que a computação de um programa possa ser descrita.
Cabe à máquina suprir as funções de entrada e de saída, ou seja, o armazenamento ou recuperação de informações na estrutura de memória; e o significado aos identificadores das operações e testes.
TEORIA DA COMPUTAÇÃO
Máquinas: Definição formal
Uma máquina é uma 7-upla M = (V, X, Y, πx, πy, ΠF, ΠT), onde: V é um conjunto de valores de memóriaX é o conjunto de valores de entradaY é o conjunto de valores de saídaπx:X → V é uma função de entradaπy:V → Y é uma função de saídaΠF: conjunto de interpretações de operações
πF:V → V em ΠF
ΠT : conjunto de interpretações de testes πT:V → {verdadeiro, falso} em ΠT
TEORIA DA COMPUTAÇÃO
Máquinas: Definição formal
As funções acima são totais.
Há uma interpretação para cada identificador de operação
e teste nos conjuntos ΠF e ΠT. Esses conjuntos podem ser vistos
como um conjunto de funções indexado pelo subconjunto de
identificadores de operações e testes para os quais a máquina é
definida.
P é um programa para máquina M se cada identificador de teste e operação em P tiver uma correspondente função de teste e operação em M.
A máquina pode possuir operações ou testes sem correspondência no programa.
TEORIA DA COMPUTAÇÃO
Máquinas:
Exemplo: Máquina de 2 registradores• Suponha uma especificação de uma máquina com 2
posições de memória, denominadas registradores a e b, os quais assumem valores em N, com duas operações e um teste, como segue:
• subtração de 1 em a, se a > 0• adição de 1 em b• teste se a é zeroAdicionalmente a entrada a é constituída de umúnico valor armazenado em a, zerando b, e a saída retorna o valor de b.
TEORIA DA COMPUTAÇÃO
Máquinas: Exemplo:
Dois_reg = (N2 , N, N, armazena_a, retorna_b, {subtrai_a, adiciona_b}, {a_zero}) onde:
N2 é o conjunto de valores de memóriaN é o conj. de valores de entrada e de saídaarmazena_a: N → N2 é a função de entrada tal que para qualquer n pertencente a N
armazena_a(n) = (n, 0)retorna_b: N2 → N é a função de saída tal que para quaisquer n, m pertencente a N2
retorna_b(n, m) = m
TEORIA DA COMPUTAÇÃO
Máquinas:
subtrai_a: N2 → N2 é a interpretação tal que para todo n, m pertencente a N2
subtrai_a(n, m) = (n-1, m) se n > 0 e subtrai_a(n, m) = (0, m) se n = 0
adiciona_b: N2 → N2 é a interpretação tal que para todo n, m pertencente a N2
adiciona_b(n, m) = (n, m+1)
a_zero: N2 → {verdadeiro, falso} é interpretação tal que para todo n, m pertencente a N2
a_zero(n, m) = V se n = 0 e a_zero(n, m) = F se n diferente de zero
TEORIA DA COMPUTAÇÃO
Máquinas: Programas para a máquina Dois_reg
Iterativo Recursivo
até a_zerofaça (subtrai_a; adiciona_b)
rec é R ondeR def (se a_zero então ν senão S;
R ),S def subtrai_a; adiciona_b
O que fazem os programas acima?
Atribuem o valor armazenado em a ao registrador b.
TEORIA DA COMPUTAÇÃO
Computação:
Uma computação é o histórico do funcionamento da máquina para o programa, considerando um valor inicial.
Uma computação de um programa em uma máquina para uma dada entrada é uma sequencia de configurações a qual define passo a passo a execução do programa na máquina.
TEORIA DA COMPUTAÇÃO
Computação:
Computação de um programa monólitico: é um histórico das instruções executadas e o correspondente valor de memória. O histórico é representado por uma cadeia de pares ordenados onde:
• cada par ordenado reflete uma descrição instantanea da máquina para o programa (instrução executada, valor corrente de memória)
• a cadeia de pares é a sequencia de configurações possíveis a partir da configuração inicial
TEORIA DA COMPUTAÇÃO
Computação:
Definição formal:Sejam M = (V, X, Y, πx, πy, ΠF, ΠT) uma máquina e P = (I, r) um programa monolítico para M. L é o seu correspondente conjunto de rótulos. Uma computação do programa monolítico P na máquina M, para uma dada entrada x, é uma cadeia de descrições instantaneas em L x V:
(s0, v0) (s1, v1) (s2, v2)...
A configuração inicial (s0, v0) é tal que s0 = r e v0 =πx(x). Para cada configuração (sk,vk) da cadeia, onde k pertence {0,1,2,...} tem-se que:
TEORIA DA COMPUTAÇÃO
Computação:
Operação:• Se sk é o rótulo de uma operação da forma sk: faça F e vá
para r' então a próxima descrição instantânea será (sk+1, vk+1) = (r', πf(vk))
• Se sk é o rótulo de uma operação da forma sk: faça ν e vá para r' então a próxima descrição instantânea será
(sk+1, vk+1) = (r', vk)Teste Se sk é o rótulo de um teste da forma sk: se T então vá para r' senão vá para r'' então (sk+1, vk+1) = (r', vk) se πT(vk
) for verdadeiro e
(sk+1, vk+1) = (r'', vk) se πT(vk) for falso.
TEORIA DA COMPUTAÇÃO
Computação:
Uma computação é dita finita ou infinita, se a cadeia que a define é finita ou infinita.
Sendo finita, o rótulo da última configuração da cadeia é um rótulo final.
Em uma computação infinita, rótulo algum da cadeia é final.
TEORIA DA COMPUTAÇÃO
Computação:
Ex: Sejam os programas monolíticos para a máquina Dois_reg:
1: se a_zero então vá_para 9 senão vá_para 22: faça subtrai_a vá_para 33: faça adiciona_b vá_para 1
1: faça adiciona_b vá_para 1
Apresente a computação dos programas na máquina Dois_reg para a entrada 3, o que corresponde ao valor inicial de memória (3, 0)
TEORIA DA COMPUTAÇÃO
Computação:
Computação de um programa recursivo: o histórico é representado por uma cadeia de pares ordenados onde:
• cada par ordenado reflete uma descrição instantânea da máquina para o programa (expressão de sub-rotina, valor corrente de memória)
• a cadeia de pares é a sequencia de configurações possíveis a partir da configuração inicial (expressão de sub-rotina inicial e valor de memória considerado)
TEORIA DA COMPUTAÇÃO
Computação:
Definição formal: Sejam M = (V, X, Y, πx, πy, ΠF, ΠT) uma máquina e P um programa recursivo para M tal que:
P é E0 onde R1 def E1, R2 def E2, ..., Rn def Em
Uma computação do programa recursivo na máquinaM é uma cadeia de descrições instantaneas da forma: (D0, v0) (D1, v1) (D2, v2)...
A configuração incial (D0, v0) é tal que D0 = E0; ν e v0 = πx(x)
TEORIA DA COMPUTAÇÃO
Computação:
Para cada par (Dk, vk) da cadeia, onde k pertence {0, 1, 2, ...}tem-se que (suponha que F é um identificador de operação, T é um identificador de teste e C, C1, C2 são expressões de subrotina)• Se Dk é uma expressão de sub-rotina da forma: Dk = ν; C,então, a configuração subsequente, (Dk+1, vk+1) = (C, vk)• Se Dk é uma expressão de sub-rotina da forma: Dk = F; C,então, a configuração subsequente, (Dk+1, vk+1) = (C, πx(vk))• Se Dk é uma expressão de sub-rotina da forma: Dk = Ri; C,então, a configuração subsequente, (Dk+1, vk+1) = (Ei;C, vk).
Observe que primeiro é executada a expressão Ei da definição da sub-rotina Ri.
TEORIA DA COMPUTAÇÃO
Computação:
• Se Dk é uma expressão de sub-rotina da forma: Dk = (C1; C2); C, então a configuração subsequente(Dk+1, vk+1) = (C1; (C2;C), vk).
• Se Dk é uma expressão de sub-rotina da forma: Dk = Ek = (se T então C1 senão C2); C, então a configuração subsequente (Dk+1, vk+1) caracteriza o desvio condicional como segue:Vk + 1 = vk
Dk+1 = C1; C se πT(vk) = verdadeiroDk+1 = C2; C se πT(vk) = falso
TEORIA DA COMPUTAÇÃO
Computação:
A computação é finita ou infinita, se a cadeia que a define é finita ou infinita.
Em uma computação finita, na configuração final e apenas nesta a expressão é ν
Em uma computação infinita, expressão alguma da cadeia é ν.
TEORIA DA COMPUTAÇÃO
Computação:
Ex: Apresente a computação do programa recursivo abaixo em qualquer máquina:
Qq_maquina é R onde R def R
TEORIA DA COMPUTAÇÃO
Computação:
Exercício:Seja a máquina um_reg apresentada abaixo
Um_reg = (N, N, N, idN, idN, {ad, sub}, {zero})N é o conj. de valores de memória, de entrada e saídaidN: N -> N é a função de entrada e de saída (idN(a) = a)ad: N -> N é interpretação tal que, para todo n pertencente a N, ad(n) = n + 1sub: N-> N é interpretação tal que, para todo n pertencente a N, sub(n) = n-1 se n diferente de 0 e sub(n) = 0, se n = 0;zero: N -> {V, F} é interpretação tal que, para todo n pertencente a N, zero(n) = verdadeiro, se n = 0; zero(n) =falso, caso contrário.
TEORIA DA COMPUTAÇÃO
Computação:
Exercício:Seja o programa duplica para máquina um_reg
Duplica é R onde R def (se zero então v senão (sub; R; ad; ad))
Apresente a computação para valor inicial de memória igual a 2.
TEORIA DA COMPUTAÇÃO
Função computada:
A computação de um programa deve ser associada a uma entrada e uma saída.
Uma função computada é o resultado que foi obtido no final de uma computação sendo esta computação finita.
TEORIA DA COMPUTAÇÃO
Função computada:
Função computada por programa monolítico:
• A computação inicia na instrução identificada pelo rótulo inicial com a memória contendo o valor inicial resultante da aplicação da função de entrada sobre o dado fornecido;
• Executa, passo a passo, testes e operações, na ordem determinada pelo programa, até atingir um rótulo final, quando para;
• o valor da função computada pelo programa é o valor resultante da aplicação da função de saída ao valor da memória quando da parada.
TEORIA DA COMPUTAÇÃO
Função computada:
Função computada por programa monolítico:Definição formal: Sejam M = (V, X, Y, πx, πy, ΠF, ΠT) uma
máquina e P um programa monolítico.
A função computada pelo programa monolítico P na máquina M denotada por: <P, M> : X → Y é uma função parcial definida para x em X se a cadeia: (s0,v0) (s1, v1), … (sn, vn) é uma computação finita de P em M.
A imagem de x é dada pela função de saída aplicada ao valor da memória da configuração final da computação, ou seja: <P, M> (x) = πy(vn)
Obs.: Se a cadeia que representa a computação é infinita, a função computada não é definida para o valor de entrada.
TEORIA DA COMPUTAÇÃO
Função computada:
Função computada por programa recursivo:• A computação inicia na expressão de sub-rotina inicial
concatenada com a expressão vazia e com a memória contendo o valor inicial resultante da aplicação da função de entrada sobre o dado fornecido;
• Executa, passo a passo, testes e operações, na ordem determinada pelo programa, até que a expressão de sub-rotina resultante seja a expressão vazia, quando para;
• o valor da função computada pelo programa é o valor resultante da aplicação da função de saída ao valor da memória quando da parada.
TEORIA DA COMPUTAÇÃO
Função computada:
Função computada por programa recursivo:Definição formal: Sejam M = (V, X, Y, πx, πy, ΠF, ΠT) uma máquina e P um programa recursivo. A função computada pelo programa recursivo P na máquina M denotada por:
<P, M> : X → Y é uma função parcial definida para x em X se a cadeia: (D0,v0) (D1, v1), … (Dn, vn) é uma computação finita de P em M quando Dn = ν.
Neste caso, a imagem de x é dada pela função de saída aplicada ao valor da memória da configuração final da computação, ou seja: <P, M> (x) = πy(vn)
Obs.: Se a cadeia que representa a computação é infinita, a função computada não é definida para o valor de entrada.
TEORIA DA COMPUTAÇÃO
Equivalência de programas e máquinas:
Relação de equivalência forte de programas: 2 programas pertencem à relação se as correspondentes funções computadas coincidem para qualquer máquina.
Relação de equivalência de programas em uma máquina: 2 programas pertencem à relação se as correspondentes funções computadas coincidem para uma dada máquina.
Relação de equivalência de máquinas: 2 máquinas pertencem à relação se as máquinas podem se simular mutuamente.
TEORIA DA COMPUTAÇÃO
Equivalência de programas e máquinas:
Para esse estudo, considere o seguinte:
• Igualdade de funções parciais: Duas funções f, g: X → Y são ditas iguais, ou seja, f = g, se, e somente se, para cada x pertencente a X:Ou f(x) e g(x) são indefinidas;Ou ambas são definidas e f(x) = g(x)
• Composição sucessiva de funções: Para uma dada função f: S → S, a composição sucessiva de f com ela própria é denotada usando expoente, ou seja: fn = f o f... o f (n vezes)
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Sejam P e Q dois programas arbitrários, não necessariamente do mesmo tipo. Então o par (P, Q) está na relação de equivalência forte de programas, denotado por: P ≡ Q, se, e somente se, para qualquer máquina M, as correspondentes funções parciais computadas são iguais, ou seja: <P, M> = <Q, M>
Neste caso, P e Q são ditos programas fortemente equivalentes.
Considere os programas P1, P2, P3 e P4 abaixo:
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Eles são todos fortemente equivalentes.Como demonstrar que 2 deles são fortemente
equivalentes?Vamos demonstrar para o P1 e P4. Podemos
reescrever o P1 na forma de instruções rotuladas:
1: se T então vá para 2 senão vá para 32: faça F e vá para 1
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Sejam M = (V, X, Y, πx, πy, ΠF, ΠT) uma máquina qualquer e x X tal que ∊ πx(x) = a. Então, se <P1, M> é definida para x, a correspondente computação é dada por:
(1, a) (2, a) (1,πF(a) ) (2, πF(a)) (1, πF2(a)) (2, πF
2(a))…(1, πFn(a)) (3, πF
n(a))
Supondo que n é o menor natural tal que πT(πFn(a)) = F.
Neste caso: <P1,M> (x) = πY(πFn(a))
1: se T então vá para 2 senão vá para 32: faça F e vá para 1
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Analogamente, se <P4, M> é definida para x, a correspondente computação é apresentada abaixo:
P4 é R onde R def (se T então F; R senão v)
(R; v, a) ((se T então F; R senão v); v, a) ((F;R); v, a) (F; (R); v, a) (R; v, πF(a))
((se T então F; R senão v); v, πF(a))
((F; R); v, πF(a))
(F;( R); v, πF(a))
(R; v, πF2(a))
... ((se T então F; R senão v); v, πF
n(a))
(v; v, πFn(a))
(v, πFn(a))
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Supondo que n é o menor natural tal que πT(πFn(v)) = F.
Neste caso: <P4,M> (x) = πY(πFn(v)).
Portanto, P1 ≡ P4, pois para qualquer máquina M, tem-se que: <P1, M> = < P4, M>
É importante considerar a relação de equivalência forte de programas principalmente para analisar a complexidade estrutural dos programas. Por exemplo, o programa P1 é estruturalmente mais otimizado que P2 pois contém um teste a menos.
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Resultados sobre tipos de programas:
• Para todo iterativo, existe um monolítico fortemente equivalente (iterativo → monolítico).
• Para todo monolítico, existe um recursivo fortemente equivalente (monolítico → recursivo).
A inversa não é necessariamente verdadeira.
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Iterativo → monolítico (prova por construção)Para qualquer programa iterativo P
i, existe um monolítico P
m, tal
que Pi ≡ P
m
Seja Pi um programa iterativo qualquer. Seja P
m um programa
monolítico indutivamente construído como segue:
• Para operação v corresponde o seguinte fluxograma:
ou simplesmente
• Para cada identificador de operação F de Pi corresponde o
fluxograma: vF
vv
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Suponha que T é um identificador de teste e que V, W são programas iterativos usados na construção de P
i. Para
cada tipo de composição apresentada o correspondente fluxograma de P
m:
Composição sequencial: V; W
Composição condicional: se T então V senão W
V W
V WTv f
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Composição enquanto: enquanto T faça V
Composição até: até T faça V
T Vv
f
T Vv
f
T Vf
v
T V
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
monolítico → recursivo (prova por construção)Para qualquer programa monolítico P
m, existe um recursivo P
r,
tal que Pm ≡ P
r
Seja Pm um programa monolítico qualquer onde L = {r
1, r
2, ..., r
n}
é o conjunto de rótulos e rn é o rótulo final. Então, P
r é um
programa recursivo construído a partir de Pm e é tal que:
Pr é R
1 onde R
1 def E
1, R
2 def E
2, ..., R
n def v onde para K ∊ {1,
2, ..., n-1} , Ek é como segue:
• Operação. Se a instrução rotulada rk é da forma:
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
rk: faça F vá para r
k'
então a Ek é: F;R
k'
• Teste. Se a instrução rotulada rk é da forma:
rk: se T então vá para r
k' senão vá para r
k''
Então Ek é: se T então R
k' senão R
k''
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Como já foi dito, a inversa não é necessariamente verdadeira. Basta mostrar um contraexemplo:
• Tente apresentar um programa monolítico para o programa recursivo duplica:
Duplica é R onde R def (se zero então v senão (sub; R; ad; ad))
TEORIA DA COMPUTAÇÃO
Equivalência forte de programas:
Considere um programa monolítico chamado par para máquina um_reg, onde a correspondente função 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
• Apresente o programa monolítico par na forma de fluxograma.
• Tente apresentar um programa iterativo para o programa monolítico par.
TEORIA DA COMPUTAÇÃO
Equivalência de programas:
Pode ser desejado analisar a equivalência de programas em uma dada máquina.
Sejam P e Q dois programas arbitrários, não necessariamente do mesmo tipo, e uma máquina M. Então o par (P, Q) está na relação de equivalência de programas na máquina M, denotado por P ≡M Q se e somente se, as correspondentes funções parciais computadas são iguais, ou seja, <P, M> = <Q, M>.
Neste caso, P e Q são ditos programas equivalentes na máquina M, ou simplesmente programas M-equivalentes.
TEORIA DA COMPUTAÇÃO
Equivalência de máquinas:
Simulação forte de máquinas: Sejam M = (VM, X, Y, πxM,
πyM, ΠFM, ΠTM) e N = (VN, X, Y, πxN, πyN, ΠFN, ΠTN) duas
máquinas arbitrárias. N simula fortemente M se, e somente se, para qualquer programa P para M, existe um programa Q para N tais que as correspondentes funções parciais computadas coincidem, ou seja
<P, M> = <Q, N>
Observe que a simulação forte de uma máquina por outra pode ser feita usando programas diferentes;
E que a igualdade de funções exige que os conjuntos domínio e contradomínio sejam iguais.
TEORIA DA COMPUTAÇÃO
Equivalência de máquinas: Simulação de máquinas: Sejam M = (V
M, X
M, Y
M, πxM,
πyM, ΠFM, ΠTM) e N = (VN, X
N, Y
N, πxN, πyN, ΠFN, ΠTN) duas
máquinas arbitrárias. N simula M se, e somente se, para qualquer programa P para M, existe um programa Q para N e existem:
Função de codificação c: XM
→ X
N
Função de decodificação: d: YN → Y
M
Como N simula M?
TEORIA DA COMPUTAÇÃO
Equivalência de máquinas:
Sejam M e N duas máquinas arbitrárias. Então o par (M, N) está na relação de equivalência de máquina, se, e somente se:
M simula N e N simula M.
TEORIA DA COMPUTAÇÃO
Referências
DIVERIO, T. A.; MENEZES, P. B.. Teoria da Computação: Máquinas Universais e Computabilidade. Porto Alegre: Sagra Luzzato, 2000.