Apostila do curso
Teoria da Computac~ao
Modelos de computac~ao
David Deharbe
Periodo 98.1
Indice
1 Introduc~ao
1.1
1.2
1.3
1.4
Denic~oes basicas e terminologia . . . . . . . .
Objetivos . . . . . . . . . . . . . . . . . . . . .
Computabilidade . . . . . . . . . . . . . . . . .
Primeiros contatos com a teoria da computac~ao
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.1 Introduc~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Func~oes Primitivas Recursivas . . . . . . . . . . . . . . . . . . .
3.2.1 Denic~ao . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3 Programac~ao de func~oes primitivas recursivas na MAR .
3.2.4 Totalidade . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Func~oes parciais recursivas . . . . . . . . . . . . . . . . . . . . .
3.3.1 Denic~oes . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Computabilidade MAR . . . . . . . . . . . . . . . . . .
3.4 Equival^encia de MAR e func~oes parciais recursivas . . . . . . .
3.4.1 Codicac~oes s~ao func~oes primitivas recursivas . . . . . .
3.4.2 Codicac~ao de programas MAR . . . . . . . . . . . . . .
3.4.3 Simulac~ao da Execuc~ao de Programas MAR . . . . . . .
3.5 A tese de Church . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.1 Provas com a tese de Church . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Maquinas de acesso rand^omico
2.1 Introduc~ao . . . . . . . . . . . . . . . . .
2.2 Denic~oes . . . . . . . . . . . . . . . . .
2.2.1 Exemplo: soma de dois naturais
2.2.2 Exerccios . . . . . . . . . . . . .
2.3 Observaco~es . . . . . . . . . . . . . . . .
2.3.1 Numero de registros usados . . .
2.3.2 Um modelo mais basico . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Func~oes Parciais Recursivas
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
2
2
3
3
6
6
6
7
7
7
7
7
9
9
9
9
10
12
13
14
14
15
15
15
17
19
21
21
1.
Introduc~ao
1.1 Denic~oes basicas e terminologia
Uma denic~ao intuitiva da computac~ao e:
A computac~ao e o transporte e a transformac~ao de dados (ou de informac~ao). As transformac~oes s~ao realizadas por passar dados atraves de entidades chamados de processadores.
Exemplos de processadores e de computac~oes s~ao:
Um computador:
Um circuito integrado:
Um televisor:
Usaremos o termo de func~ao no sentido matematico do termo.
Um algortmo, ou procedimento, ou programa, e um metodo automatico que permite calcular uma
func~ao. Entendemos que os programas devem ser compostos de etapas basicas que podem ser realizadas
automaticamente, por uma maquina.
Um exemplo de func~ao e a adic~ao de dois numeros inteiros. Aprendemos na escola como calcular
essa func~ao, por uma sequ^encia de passos simples que necessitam nenhuma intelig^encia propria a o
homem, e que portanto podem ser automatizados. Alias calculadoras s~ao exemplos de maquinas que s~ao
programadas para calcular essa func~ao.
Uma linguagem de programac~ao e uma linguagem formal que serve para programar processadores.
S~ao as linguagens de programac~ao que permitem denir programas. Cada linguagem de programac~ao e
composto de um numero enumeravel de smbolos e programas s~ao sequ^encias de tais smbolos.
1.2 Objetivos
A teoria da computac~ao tem como objetivo o estudo das propriedades fundamentais dos sistemas de
computac~ao, independentemente dos paradigmas de programac~ao usados em pratica. Os resultados se
aplicam tanto aos programas desenvolvidos em linguagem de programac~ao imperativa, funcional ou logica,
orientada a objeto ou n~ao, sequ^encial ou concorrente.
Portanto os resultados obtidos na area da teoria da computac~ao tem as caractersticas seguintes:
eles s~ao resultados abstratos, e geralmente n~ao v~ao poder ser aplicados direitamente para melhorar
sua maneira de usar linguagens de programac~ao;
mas eles s~ao resultados gerais, que s~ao verdadeiros tanto para programas e linguagens de programac~ao contempor^aneos quanto para os futuros.
Temos a propriedade interessante seguinte:
Os resultados da teoria da computac~ao s~ao independentes da tecnologia.
Enm e interessante e pertinente notar que a maioria dos resultados apresentados nesse curso foram
obtidos no incio da decada de 30, quando ainda n~ao havia computadores.
2
Captulo 1. Introduc~ao
3
1.3 Computabilidade
Uma func~ao e computavel se existe alguma possibilidade de calcular ela de maneira autom^atica, sem
nenhuma restric~ao de espaco nem de tempo. Se uma func~ao e computavel, existe um programa que
calcula ela. E um objetivo da teoria da computabilidade estuda o que computadores podem realizar.
Exemplo: Considera as func~oes seguintes:
1. Soma de dois inteiros.
2. Achar o n-esimo numero primo.
3. Derivac~ao de uma func~ao polinomial.
4. Maior divisor comum de dois numeros naturais.
5. x e y sendo dois numeros naturais, decidir se x e um multiplo de y.
Existe programas computando cada uma dessas funco~es. Essas func~oes s~ao computaveis.
Exemplo: Considera a func~ao seguinte:
f : n 7!
1 se existe uma sequ^encia de n 7 na frac~ao decimal de .
0 sen~ao
Exerccio: Sabendo que existe um programa P que gera a sequ^encia de algarismos da frac~ao decimal
do numero , f e computavel ?
Resposta: Um programa para calcular f poderia ser:
Dado n, comecar a gerar a frac~ao decimal de , com o programa P , e prestar atenc~ao aos
7. Se, a algum momento, ha n 7 consecutivos, parar o programa e o resultado sera 1, sen~ao o
resultado sera 0.
O problema desse programa e se n~ao ha uma sequ^encia de n 7 consecutivos no numero , ele nunca
terminara. Portanto esse programa n~ao e um procedimento efetivo, pois n~ao tem garantia que termina
para alguns valores de n.
Em geral, se P e um programa de que tem um par^ametro natural e o resultado e um natural, o sentido
de P , ou a sem^antica de P e uma func~ao f : IN ! IN. Se o programa n~ao termina para alguns valores de
entrada, f e parcial e e notada IN?IN.
1.4 Primeiros contatos com a teoria da computac~ao
No paragrafo precedente, encontramos um exemplo de programa que n~ao termina para alguns valores de
entrada. Evidentemente, a gente gostaria ter uma linguagem de programac~ao tal que todos os programas
terminam, por qualquer valor de entrada. Uma linguagem de programac~ao e total se qualquer programa
dessa linguagem e total.
Uma linguagem de programac~ao e universal se qualquer func~ao computavel pode ser programada
nessa linguagem. Veremos varias linguagens de programac~ao universais nesse curso, e veremos tambem
exemplos de func~oes n~ao computaveis.
Teorema 1.1 Se a linguagem de programac~ao L e universal, ent~ao existe programas de L que n~ao
terminam.
Uma consequ^encia desse teorema e que devemos escolher entre linguagens de programac~ao universais
e totais.
Prova:
(Por diagonalizac~ao e contradic~ao) Seja L uma linguagem de programac~ao. E possvel enumerar todos
Captulo 1. Introduc~ao
4
os programas de L: P0 ; P1 ; : : : Pn ; : : :, por exemplo em ordem de tamanho crescente. Como L tem um
numero nito de smbolos, ha um numero nito de programas com um certo tamanho, que podem ent~ao
ser ordenados por ordem alfabetica.
Seja fn : N ! N a func~ao computada por Pn , por todo n.
Fazemos a hipotese seguinte:
1. L e universal,
2. e todos os programas de L s~ao totais.
Seja fn a func~ao computada por o programa Pn . Seja g denida por:
g: N !N
n 7! fn(n) + 1
g e uma func~ao denida por todo n.
Seja Pg o programa calculando g:
Sendo a entrada n, gerar a lista dos n primeiros programas de L. Executar Pn sobre n e
incrementar o resultado.
Como L e uma linguagem de programac~ao universal, g dever ser computada por algum programa de
L. Seja Pm esse programa. Em consequ^encia g(m) = fm(m). Mas, por denic~ao de g, g(m) = fm (m)+1.
Ha contradic~ao e a hipotese deve ser rejeitada.
N
Uma outra maneira de explicar o teorema e imaginar a enumerac~ao de todas as func~oes computadas
por programas de L:
f0 : f0 (0) f0 (1) f0 (2) : : :
f1 : f1 (0) f1 (1) f1 (2) : : :
f2 : f2 (0) f2 (1) f2 (2) : : :
..
..
..
..
.
.
.
.
Na diagonal, g e diferente de fn , ent~ao g n~ao pode fazer parte dessa enumerac~ao e L n~ao e universal.
A consequ^encia desse teorema e que temos que escolher entre
1. uma linguagem de programac~ao universal, mas que tem programas que n~ao s~ao totais.
2. uma linguagem de programac~ao que garante que todos os programas terminam, mas na qual n~ao e
possvel programar certas func~oes.
Teorema 1.2 Existe funco~es n~ao computaveis.
Prova:
Seja L uma linguagem universal, com programas P0 ; : : : Pn : : : e func~oes correspondentes f0 ; : : : fn : : :.
g(n) =
fn (n) + 1 se fn e denido
0
sen~ao
Hipotese: g e computavel.
L e universal, portanto:
9m : N g = fm .
g e fm n~ao s~ao necessariamente totais (teorema 1).
Considera ent~ao g(m):
Captulo 1. Introduc~ao
5
1. se fm (m) e denida, ent~ao g(m) = fm (m) + 1 6= fm (m), e ha contradic~ao nesse caso;
2. se fm (m) n~ao e denida, ent~ao g(m) = 0 6= fm (m), e ha tambem contradic~ao nesse caso.
N
Portanto, devemos rejetar a hipotese que g e computavel. Existe func~oes que n~ao s~ao computaveis.
A func~ao g usada nessa demonstrac~ao n~ao e muito util, mas veremos nesse curso exemplos de func~oes
importantes, ligadas a problemas de decis~ao, que n~ao s~ao computaveis:
1. Problema da parada: Sera que o programa P termina sua execuc~ao com o valor da entrada n ?
2. Problema da decibilidade da logica dos predicatos: Sera que a formula e um teorema ?
2.
Maquinas de acesso rand^omico
2.1 Introduc~ao
Informalmente, um computador pode ser considerado como sendo composto de uma memoria e de uma
unidade de computaca~o, chamada tambem de processador. Os primeiros modelos de computadores
tinham ou um acesso sequencial, com uma memoria baseada no modelo de ta (caso da maquina de
Turing), ou eram puramente funcional, sem memoria explcita (caso do -calculo de Church).
O acesso rand^omico signica que o processador pode acessar direitamente qualquer parte da memoria,
com seu endereco.
2.2 Denic~oes
O modelo de Maquina de Acesso Rand^omico (MAR) tem um conjunto de instruc~oes basicas e uma
memoria composta de um numero innito de registros. Cada registro pode armazenar um numero natural
e pode ser referenciado por seu endereco. O estado da maquina de acesso rand^omico e ent~ao uma funca~o
totoal MEM : IN ! IN. Cada instruc~ao pode ter um rotulo associado a ela. As instruc~oes da MAR s~ao:
Incrementac~ao INC Ri incrementa de 1 o conteudo do registro Ri .
Decrementac~ao DEC Ri decrementa de 1 o conteudo do registro Ri .
Zerac~ao CLR Ri zera o conteudo do registro Ri .
Atribuic~ao Ri Rj atribui ao registro Ri o conteudo de Rj . O conteudo de Rj n~ao e alterado.
Pulo incondicional JMP Nix Se x = a (como acima), a proxima instruc~ao a ser executada e a mais
proxima instruc~ao precedente com rotulo Ni . Se x = b (como baixo), a proxima instruc~ao a ser
executada e a mais proxima instruc~ao seguinte com rotulo Ni .
Pulo condicional Rj JMP Nix. Realiza uma instruca~o JMP se o conteudo do registro Rj e 0.
Nula CONTINUE faz nada.
Denic~ao 2.1 (Programa MAR) Um programa MAR e uma sequ^encia nita de instruc~oes tal que
cada instruc~ao JMP (tipo 5 ou 6) tem uma destinac~ao valida, e tal que a ultima instruc~ao seja CONTINUE.
Denic~ao 2.2 (Parada) Um programa MAR para se e quando ele atinge a ultima instruc~ao.
Denic~ao 2.3 (Computac~ao de func~ao) Um programa MAR P calcula uma func~ao parcial f : INn !
IN se, quando P e inicializado com os valores x1 ; : : : xn nos registros R1 ; : : : Rn , e os valores nos demais
registros, ent~ao P para se f (x1 ; : : : xn ) e denido e o conteudo de R1 e f (x1 ; : : : xn ).
Denic~ao 2.4 (Func~ao MAR-computavel) Uma func~ao parcial f e MAR-computavel se existe um
programa MAR P que calcula f .
Portanto, para mostrar que uma func~ao e MAR-computavel, basta achar um programa que calcula
essa func~ao.
6
Captulo 2. Maquinas de acesso rand^omico
7
2.2.1 Exemplo: soma de dois naturais
A soma e uma func~ao total, portanto o programa MAR Ps que calcula a soma deve parar por qualquer
valores. Ent~ao, quando Ps e inicializado com dois valores x1 e x2 nos registros R1 e R2 , e o valor 0 nos
demais registros, Ps para com o valor x1 + x2 no registro R1 . O programa seguinte satisfaz essas condic~oes:
(1)
(2)
(3)
(4)
(5)
fR1 + R2 = x1 + x2 g
N1 R2 JMP N2b
f(R1 + R2 = x1 + x2 ) ^ (R2 6= 0)g
INC R1
f(R1 + R2 = x1 + x2 + 1) ^ (R2 6= 0)g
DEC R2
fR1 + R2 = x1 + x2 g
JMP N1a
fR1 + R2 = x1 + x2 g
f(R1 + R2 = x1 + x2 ) ^ (R2 = 0)g
, f(R1 = x1 + x2 ) ^ (R2 = 0)g
N2 CONTINUE
Colocamos a esquerda do programa uma prova informal que Ps calcula bem a soma. Entre cada instruc~ao
e dado um predicado (uma condic~ao) sobre os valores dos registros da maquina. Quando a ultima instruc~ao
e executada, o conteudo de R1 e bem x1 + x2 . O predicado que precede uma instruc~ao e a pre-condic~ao
e o que segue e a pos-condic~ao. Obviamente, a pos-condica~o de uma instruc~ao que n~ao for um pulo deve
ser igual a pos-condic~ao da instruc~ao seguinte.
2.2.2 Exerccios
1. Mostrar que a multiplicac~ao e MAR-computavel.
2. Mostrar que a substrac~ao propria e MAR-computavel. A substrac~ao propria e denida por:
;_ : IN2 ! IN
x1 ; x2 se x1 x2
(x1 ; x2 ) 7!
0 se x1 x2
3. Mostrar que a exponenciac~ao e MAR-computavel.
4. Mostrar que o maior divisor comum e MAR-computavel.
2.3 Observac~oes
2.3.1 Numero de registros usados
Mesmo se a memoria da MAR contem um numero innito de registros, um programa MAR acessa so
uma quantidade nita de registros durante uma computac~ao que termina. Se a computac~ao n~ao termina,
ela dura um tempo innito e pode usar um numero innito de registros.
2.3.2 Um modelo mais basico
Teorema 2.1 Por qualquer programa MAR P , existe um programa MAR P 0 que usa so instruc~oes dos
tipos 1, 2, 6 e 7.
Captulo 2. Maquinas de acesso rand^omico
8
Prova Para provar esse teorema, vamos mostrar como reescrever as instruc~oes 3, 4 e 5 em func~ao das
instruc~oes 1, 2, 6 e 7:
1. instruc~ao 4 (atribuic~ao) em func~ao de 1, 2, 3, 5, 6, 7.
Nk
P
Ri
Rj
;! P1
;! Nk
Nc
Nd
Nc
CLR Ri
CLR Rn
JMP Nd b
DEC Rj
INC Ri
INC Rn
JMP Nc a
Rn JMP Nc b
DEC Rn
INC Rj
JMP Nd a
CONTINUE
2. instruc~ao 3 (zerac~ao) em func~ao de 1, 2, 5, 6, 7.
Nk
P1
CLRRi
;! P2
;! Nk
Nc
Ri JMP Nc b
DEC Ri
JMP Nk a
CONTINUE
3. instruc~ao 5 (salto incondicional) em func~ao de 1, 2, 6 e 7.
Nk
;! P 0
JMPNi x ;! Nk
P2
CLRRj
Rk JMP Nk a
3.
Funco~es Parciais Recursivas
3.1 Introduc~ao
Nesse captulo, e denido um novo modelo de computac~ao, chamado de func~oes primitivas recursivas
(FPiR), formadas a partir de func~oes basicas e operac~oes de construc~ao de func~oes. FPiR formam um
modelo de computac~ao completamente funcional . Veremos que toda FPiR e total e computavel, e que
portanto existe programas MAR que calculam func~oes que n~ao s~ao FPiR.
Isso motiva a denic~ao de um novo operador de construc~ao de func~oes, que cria a classe de func~oes
Func~oes Parciais Recursivas (FPaR). Sera ent~ao mostrado que toda FPaR e RAM-computavel, e que
todo programa RAM computa uma FPaR.
3.2 Func~oes Primitivas Recursivas
3.2.1 Denic~ao
As func~oes de base da classe das FPiR s~ao a func~ao Z (Zero), S (Successor), e o conjunto de func~oes Uji
(Projec~ao) denidas por:
!
7
!
!
7
!
8i; j : IN j j i; Uji INi !
(x1 ; : : : xi ) !
7
Z : IN
x
S : IN
x
IN
0
IN
x+1
IN
xj
(3.1)
(3.2)
(3.3)
A recurs~ao primitiva e um operador de construc~ao de func~ao. Ele tem como argumentos uma func~ao
de n par^ametros e uma func~ao de n + 2 par^ametros e produz uma nova func~ao de n + 1 par^ametros:
((INn ! IN) (INn+2 ! IN)) ! INn+1 ! IN
(g; h) 7! f tal que
f (x1 ; : : : xn ; 0) = g(x1 ; : : : xn )
f (x1 ; : : : xn ; y + 1) =
h(x1 ; : : : xn ; y; f (x1 ; : : : xn ; y)
(3.4)
Por convenc~ao, uma func~ao f : IN0 ! IN (de 0 par^ametros) e uma func~ao constante.
Exerccio: Qual e a func~ao denida por recurs~ao primitiva de Z e U13 ? Resposta: Aplicando a
denic~ao com g = Z e h = U13 :
f : IN2 ! IN
(x; 0) 7! Z (x) = 0
(x; y + 1) 7! U13 (x; y; f (x; y)) = x
Ent~ao, f (x; y) = 0 se y = 0, x sen~ao.
9
Captulo 3. Func~oes Parciais Recursivas
10
Essa forma de recurs~ao e chamada de primitiva pois f (x1 ; : : : ; xn ; y) e denida em func~ao de f (x1 ; : : : ; xn ; z ),
com z y.
A composic~ao e um segundo operador de construca~o de func~oes, e tem como argumentos uma func~ao
h de m par^ametros, e m func~oes g1 ; : : : gm de n par^ametros, e produz uma func~ao de n par^ametros:
((INm ! IN) (INn ! IN)m ) ! INn ! IN
(h; g1 ; : : : ; gn) 7! h(g1 (x1 ; : : : ; xn ); : : : gm(x1 ; : : : xm ))
Exerccio: Achar a composic~ao de Z , S , U11 por U13.
Resposta: Aplicando a denic~ao com h = U13, g1 = Z , g2 = S , e g3 = U11, temos:
(3.5)
f : IN ! IN
f (x1 ) = U13 (Z (x1 ); S (x1 ); U11 (x1 )) (denic~ao de f )
= Z (x1 ) (denic~ao de U13 )
= 0 (denic~ao de Z )
Em conclus~ao, f = Z
Denic~ao 3.1 (Func~oes primitivas recursivas) A classe das func~oes primitivas recursivas e a (menor) classe de func~oes que contem as func~oes de base e e fechada por recurs~ao primitiva e composic~ao.
3.2.2 Exemplos
Adic~ao
Para denir a FPiR Adi que calcula a adic~ao, precisamos denir uma FPiR h1 intermediaria, com 3
par^ametros e retornando o valor incrementado do seu terceiro par^ametro. h1 pode ser denida por
composic~ao das func~oes basicas S e U33 :
h1 : IN3 ! IN
(x1 ; x2 ; x3 ) 7! S (U33 (x1 ; x2 ; x3 ))
A e denida por recurs~ao primitiva de U11 e h1 :
Adi : IN2 ! IN
(x; 0) 7! U11 (x)
(x; y + 1) 7! h1 (x; y; Adi(x; y))
Exerccio: Provar que Adi(x; y) = x + y. Resposta: Lemma:
8x; y; z : IN h1 (x; y; z ) = z + 1
Ent~ao podemos provar por induc~ao sobre y que Adi e a adic~ao.
Caso de base: y = 0
Adi(x; 0) = U11 (x) (denic~ao de Adi)
= x (denic~ao de U11 )
= x + 0 (0 e elemento neutro da adic~ao)
Captulo 3. Func~oes Parciais Recursivas
11
Caso geral: A hipotese e A(x; y) = x + y.
Adi(x; y + 1) = h1 (x; y; Adi(x; y)) (denic~ao de Adi)
= h1 (x; y; x + y) (hipotese de induc~ao)
= x + y + 1 (lemma)
Agora falta provar o lemma:
8x; y; z h1 (x; y; z ) = S (U33 (x; y; z )) (denic~ao de h1
= S (z ) (denic~ao de U33
= z + 1 (denic~ao de S
Multiplicac~ao
Para denir a FPiR Mul que calcula a multiplicac~ao, precisamos denir uma FPiR h2 intermediaria,
com 3 par^ametros e retornando a soma dos primeiros e terceiros par^ametros. h2 pode ser denida por
composic~ao de U13 e U33 por Adi:
h2 : IN3 ! IN
(x1 ; x2 ; x3 ) 7! Adi(U13 (x1 ; x2 ; x3 ); U33 (x1 ; x2 ; x3 ))
Mul e denida por recurs~ao primitiva de Z e h2 :
Mul : IN2 ! IN
(x; 0) 7! Z (x)
(x; y + 1) 7! h2 (x; y; Mul(x; y))
Exerccio: Provar que Mul(x; y) = x y.
Resposta: Lemma:
8x; y; z : IN h2 (x; y; z ) = x + z
Ent~ao podemos provar por induc~ao sobre y que Mul e a multiplicac~ao.
Caso de base: y = 0
Mul(x; 0) = Z (x) (denic~ao de Mul)
= 0 (denic~ao de Z )
Caso geral: a hipotese de induc~ao e Mul(x; y) = x y.
Mul(x; y + 1) = h2 (x; y; Mul(x; y)) (denic~ao de Mul)
= h2 (x; y; x y) (hipotese de induc~ao)
= x + (x y) (denic~ao de h2 )
= x (1 + y) (fatorizac~ao de x)
= x (y + 1) (comutatividade da adic~ao)
A prova do lemma e :
8x; y; z h2 (x; y; z ) = Adi(U13 (x; y; z ); U33 (x; y; z )) (denic~ao de h2 )
= Adi(x; y) (denic~ao de U13 e U33 )
= x + y (teoremo do exerccio precedente)
Captulo 3. Func~oes Parciais Recursivas
12
3.2.3 Programac~ao de func~oes primitivas recursivas na MAR
Proposic~ao 3.1 (Computabilidade) Toda func~ao primitiva recursiva e computavel pela MAR.
Para mostrar essa proposic~ao, e suciente provar que existe um programa que calcula qualquer func~ao
primitiva recursiva.
Prova:
Essa prova e realizada por induc~ao estrutural. Mostraremos primeiro programas MAR calculando cada
func~ao de base, e depois veremos como combinar programas MAR de maneira correspondente as operaco~es
de construc~ao de FPiR: recurs~ao primitiva e composica~o
Programa para a func~ao de base Z :
N0
CLR R1
CONTINUE
Programa para a func~ao de base S :
N0
INC R1
CONTINUE
Programa para a func~ao de base Ujn :
N0
R1
Rj
CONTINUE
Programa para a recurs~ao primitiva: f : INn+1 ! IN e denida por recurs~ao primitiva de g e h. Pg e
Ph s~ao programas MAR que calculam g e h. Informalmente, o algoritmo que calcula f (x1 ; : : : xn ; y)
calcula a sequ^encia dos termos seguintes:
f (x1 ; : : : xn ; 0) = g(x1 ; : : : xn )
f (x1 ; : : : xn ; 1) = h(x1 ; : : : xn ; 0; f (x1 ; : : : xn ; 0))
f (x1 ; : : : xn ; 2) = h(x1 ; : : : xn ; 1; f (x1 ; : : : xn ; 2))
..
.
f (x1 ; : : : xn ; n) = h(x1 ; : : : xn ; n ; 1; f (x1 ; : : : xn ; n ; 1))
Seja Rk+1 o primeiro registro n~ao usado pelo programa P1 ; : : : Pm . Inicialmente Pf armazena o
valor dos n primeiros par^ametros nos registros Rk+1 ate Rk+n e inicializa um contador de iterac~ao
no registro Rk+n+1 . O valor do ultimo par^ametro e armazenado no registro Rk . e uma copia do
programa Pg e executada Rk+n+2 . O teste de parada e efetuado, e se negativo os par^ametros
iniciais s~ao restorados nos registros R1 ate Rn , o valor do n + 1 e n + 2-esimos par^ametros de h s~ao
copiados nos registros Rk+n+1 e Rk+n+2 e o demais registros s~ao zerados. Uma copia do programa
Ph e executada e o valor resultado e copiado para o registro Rk+n+2 Rk e decrementado, Rk+n+1 e
incrementado e o la`co e recomecado. O valor do resultado e armazenado no registro R1 .
Programa para a composic~ao: f : INn ! IN e denida por composic~ao de g com h1 ; : : : hn . Seja Pi
os programas MAR que calculam os hi , e Pg o programa MAR que calcula g. Informalmente, o
algoritmo que calcula f (x1 ; : : : xn ; y) calcula a sequ^encia dos termos seguintes:
h1 (x1 ; : : : xn )
h2 (x1 ; : : : xn )
..
.
hm (x1 ; : : : xn )
g(h1 (x1 ; : : : xn ); h2 (x1 ; : : : xn ); : : : ; hm (x1 ; : : : xn ))
Seja Rk+1 o primeiro registro n~ao usado pelo programa P1 ; : : : Pm . O valor dos par^ametros x1 ; : : : xn
e copiado nos registros: Rk+1 ; : : : Rk+n . Por cada programa Pi , uma copia do programa Pi e executada. Depois, o resultado de Pi e copiado para o registro Rk+n+i e os registros potencialemente usados
Captulo 3. Func~oes Parciais Recursivas
N0
Rk + 1
:::
13
R1
Rk+n
Rn
CLR Rk+n+1
Rk
Rn+1
Pg
N1
Rk + n + 2
Rk JMP N2b
R1
Rk+1
R1
:::
Rn
Rk+n
Rn+1
Rk+n+1
Rn + 2 Rk+n+2
CLR R3
:::
CLR Rk;1
Ph
N2
Rk+n+2
R1
INC Rk+n+1
DEC Rk
JMP N1a
CONTINUE
Figura 3.1: Recurs~ao primitiva de programas MAR
Rn+1 ; : : : Rk
s~ao zerados. Finalmente, os resultados parciais s~ao copiados nos registros R1 ; : : : Rm ,
os demais registros s~ao zerados e uma copia do programa Pg e executada. A gura 3.2 contem o
programa resultante.
N
3.2.4 Totalidade
Proposic~ao 3.2 (Totalidade das FPiR) Func~oes primitivas recursivas s~ao totais (denidas para todos seus argumentos).
Prova:
A prova que qualquer FPiR f : INm ! IN e total e feita por induc~ao sobre n, o numero de operac~oes de
construc~ao necessarios para denir f .
Caso de base. n = 0 s~ao as func~oes de base Z , S e Uji , que s~ao totais.
Caso geral. f e denida por n + 1 operaco~es. A n + 1-esima operac~ao pode ser recurs~ao primitiva ou
composic~ao.
Se f e denida por recurs~ao primitiva de duas func~oes g e h, ambas s~ao totais por hipotese de
induc~ao H1 . Vamos mostrar por induc~ao sobre xm que f (x1 ; : : : ; xm e total.
Caso de base. f (x1 ; : : : xm;1 ; 0) = g(x1 ; : : : xm;1) e e denida por H1.
Caso geral. A hipotese de induc~ao H2 e que f (x1 ; : : : xm) e denida. Por denic~ao da recurs~ao primitiva, f (x1 ; : : : xm;1 ; xm + 1) = h(x1 ; : : : xm ; f (x1 ; : : : xm )), que e denida, por
H1 e H2 .
Portanto f e total.
Captulo 3. Func~oes Parciais Recursivas
14
Se f e denida por composic~ao das func~oes g e h1 ; : : : hk que s~ao denidas por menos de n
operac~oes, por H1 .
8x1 ; : : : xm : IN f (x1 ; : : : xm ) = g(h1 (x1 ; : : : xm ); : : : hk (x1 ; : : : xm ))
Portanto f e total.
N
Existe programas MAR que calculam func~oes n~ao totais, como evidenciado pelo exemplo seguinte:
N1 INC R1
JMP N1a
CONTINUE
Portanto a classe das func~oes computadas por programas MAR e maior que a classe das func~oes primitivas recursivas. Existe func~oes calculadas por programas MAR que n~ao s~ao primitivas recursivas. Em
consequ^encia, e criado um novo operador de construc~ao de func~oes a partir de func~oes.
3.3 Func~oes parciais recursivas
3.3.1 Denic~oes
Um novo operador de construc~ao e denido. Ele e chamado operador de minimizac~ao e corresponde a
uma operador de busca.
Denic~ao 3.2 (Operador de minimizac~ao) Uma funca~o f de n par^ametros e denida por minimizac~ao de uma func~ao h de n + 1 par^ametros quando f (x1 ; : : : xn ) e o menor y tal que h(x1 ; : : : xn ; y) = 0
e h(x1 ; : : : ; xn ; z ) e denido por todo z y. Caso um tal y n~ao existir, f (x1 ; : : : xn ) e indenido. A
notac~ao seguinte e usada para notar que f e denida por minimizac~ao da func~ao h:
f (x1 ; : : : xn ) = (y)[h(x1 ; : : : xn ; y) = 0]
Como calcular f (x1 ; : : : xn ) ? Para isso e necessario calcular a sequ^encia de valores h(x1 ; : : : ; xn ; 0); h(x1 ; : : : xn ; 1); : : :
ate encontrar um y tal que h(x1 ; : : : ; xn ; y) = 0 (e aqui que acontece a operac~ao de busca). E possvel
que n~ao existe tal y, ou que existe um z y tal que h(x1 ; : : : xn ; z ) seja indenido. E nestes casos que
f (x1 ; : : : xn ) e indenido.
Denic~ao 3.3 (Func~oes parciais recursivas) A classe das func~oes parciais recursivas e a menor classe de func~oes contendo as func~oes de base que e fechada pelas operac~oes de recurs~ao primitiva, composic~ao
e minimizac~ao.
Denic~ao 3.4 (Func~oes recursivas) A classe das func~oes recursivas e a classe de func~oes parciais
recursivas que s~ao totais.
Exerccio Provar se e verdadeiro ou falso que existe uma func~ao recursiva com domnio de chegada f0g
que n~ao e primitiva recursiva.
Antes de dar a resposta a esse exerccio, o que signca que uma func~ao recursiva n~ao seja primitiva
recursiva : ela e uma func~ao parcial recursiva, denida com o operador de minimizac~ao, e e total.
Resposta: Verdadeiro. Seja h denida por composic~ao de Z , Z e U22. h(x; y) = U22(Z (x); Z (y)). Seja
f (x) = (y)[h(x; y) = 0].
Prova que f e uma func~ao primitiva recursiva. h e denida por composic~ao de 3 func~oes de base,
h e primitiva recursiva. f e denida por minimizaca~o de h: f e uma func~ao parcial recursiva.
Captulo 3. Func~oes Parciais Recursivas
15
Prova que f e uma func~ao recursiva.
8x : IN h(x; 0) = U22 (Z (x); Z (0))
8x : IN h(x; 0) = 0
Portanto, por todo x 2 IN, f (x) e denido. f e total.
Prova que o domnio de chegada de f e f0g. Ver item precedente.
Exerccio Provar se e verdadeiro ou falso que existe uma func~ao recursiva com domnio de chegada
f0; 1g que n~ao e primitiva recursiva.
3.3.2 Computabilidade MAR
Proposic~ao 3.3 (Computabilidade) Toda func~ao parcial recursiva e computavel pela MAR.
Prova:
Como para as func~oes primitivas recursivas, essa prova e realizada por induc~ao estrutural. Mostraremos
primeiro programas MAR calculando cada func~ao de base, e depois veremos como combinar programas
MAR de maneira correspondente as operaco~es de construc~ao de func~oes parciais recursivas: recurs~ao
primitiva, composica~o e minimizac~ao. Ja tratamos o caso das func~oes de base e dos operadores de
recurs~ao primitiva e de composic~ao na prova da proposic~ao 3.1.
Falta ent~ao dar um programa MAR correspondente a minimizac~ao. Seja f uma func~ao denida por
minimizac~ao de uma func~ao h : INn+1 ! IN. Sup~oe que Ph seja um programa que calcula h. O programa
que calcula f e dado na gura 3.3.
N
3.4 Equival^encia de MAR e func~oes parciais recursivas
Ja mostramos que toda func~ao parcial recursiva pode ser computada por um programa MAR. Precisa
mostrar o inverso: que toda func~ao computada por um programa MAR e uma func~ao parcial recursiva.
Para isso, programas MAR ser~ao codicados como numeros naturais. Sera denida uma func~ao , tal
que phi(x; y1 ; : : : yn ) seja o valor obtido por rodar o x-esimo programa RAM com os par^ametros y1 ; : : : yn.
3.4.1 Codicac~oes s~ao func~oes primitivas recursivas
Ja vimos na introduc~ao como codicar pares de numeros naturais com numeros naturais. Vamos desenvolver func~oes primitivas recursivas h; i, 1 () e 2 () de codicac~ao e codicac~ao reversa tais que 1 (hx; yi) = x
e 1 (hx; yi) = y.
A tabela seguinte mostra como a codicaca~o e feita.
0 1 2 3 4 :::
0 0 2 5 9 %
1 1 4 8 %
2 3 7 %
3 6 %
..
. %
As n + 1 pares (x; y) da n-esima diagonal s~ao tais que x + y = n. O par (x; y) e o y + 1-esimo par da
n-esima diagonal. Portanto:
hx; yi = 1 + 2 + : : : + (x + y) + y
Captulo 3. Func~oes Parciais Recursivas
16
Exerccio: Mostrar que h; i e parcial recursiva.
Resposta: Para achar uma denic~ao parcial recursiva de h; i, observamos que:
8x; y : IN hx; y + 1i = 1 + 2 + : : : + (x + y + 1) + (y + 1)
=
=
=
8x : IN hx; 0i =
=
=
1 + 2 + : : : + (x + y) + (x + y + 1) + (y + 1)
1 + 2 + : : : + (x + y) + (x + 2y + 2)
hx; yi + (x + 2y + 2)
1 + 2 + : : : + (x + 0) + 0
1X
+2+:::+x
i=1
xi
Seja h10 e h11 tais que:
h10 : IN ! IN
X
x 7!
xi
i=1
h11 : IN3 ! IN
(x; y; z ) 7! x + 2y + z + 2
h; i e a recurs~ao primitiva de h11 com h10 . Agora tem que mostrar que h10 e h11 s~ao parciais recursivas.
Para mostrar que h10 e parcial recursiva, observamos que:
h10 (0) = 0
xX
+1
8x : IN h10 (x + 1) =
i=1
x
X
= (
) + (x + 1)
i=1
= h10 (x) + x + 1
Seja h12 tal que:
h12 : IN2 ! IN
(x; y) 7! x + y + 1
Basta mostrar que h12 e parcial recursiva. Observamos que h12 e a composic~ao de S e A:
8x; y : IN h12 (x; y) = S (A(x; y))
Para mostrar que h11 e parcial recursiva, observamos que:
8x; y; z : IN h11 (x; y; z ) = x + 2y + z + 2
= ((x + 2y + z ) + 1) + 1
= (((x + y) + (y + z )) + 1) + 1
= S (S (A(A(x; y); A(y; z ))))
Portanto h11 e denida por composic~oes sucessivas de S e A.
Captulo 3. Func~oes Parciais Recursivas
17
Para denir as func~oes inversas 1 e 2 , e introduzida uma func~ao auxiliar diag tal que diag(n) seja
o numero da diagonal na qual a codicac~ao n ca. n e n + 1 cam na mesma diagonal se n + 1 <
hdiag(n) + 1; 0i, ou seja se n + 2 ;hdiag(n) + 1; 0i = 0. Caso contrario, temos n + 2 ;hdiag(n) + 1; 0i = 1.
Portanto:
diag(0) = 0
_ diag(n) + 1; 0i)
8n : IN diag(n + 1) = diag(n) + ((n + 2);h
Exerccio: Mostrar que diag e primitiva recursiva.
Resposta: Informalmente:
_ y + 1; 0i)
8x; y : IN h14 (x; y) = y + ((x + 2);h
8x; y : IN h15 (x; y)
8x; y : IN h16 (x; y)
8x; y : IN h17 (x; y)
8x; y : IN h18 (x; y)
8x; y : IN h19 (x; y)
=
=
=
=
=
=
=
=
=
=
=
A(h15 (x; y); U22 (x; y))
_ y + 1; 0i)
((x + 2);h
S (S (h16 (x; y))
_ y + 1; 0i)
(x;h
Sub(U12(x; y); h17 (x; y))
hy + 1; 0i
hh18 (x; y); h19 (x; y)i
y+1
S (U22 (x; y))
0
Z (U12 (x; y))
2 (n) e a posic~ao do n-esimo par na diagonal diagn:
_ diag(n); 0i
8n : IN 2 (n) = n;h
E como 1 (n) + 2 (n) = diag(n), ent~ao:
8n : IN 1 (n) = diag(n);_ 1 (n)
Exerccio: Mostrar que 1() e 2() s~ao primitivas recursivas.
A partir da codicac~ao de pares de numeros naturais, e facil denir a codicac~ao de tuplas de n
numeros naturais. Por exemplo, hx; y; z i = hx; hy; z ii. Nota que 0 e o codigo de h0; 0i; h0; 0; 0i; ldots E
possvel denir uma func~ao de tr^es par^ametros tal que se n 2; 1 1 n, e se hz1 ; : : : ; zn i = x ent~ao
(i; n; x) = zi .
Exerccio: Mostrar que e parcial recursiva.
3.4.2 Codicac~ao de programas MAR
Consideramos so as instruc~oes basicas dos programas MAR (incrementac~ao, decrementac~ao, instruc~ao
nula, pulo condicional). Tambem consideramos que todas as instruc~oes s~ao rotuladas; se for preciso,
rotulos s~ao adicionados. Cada instruc~ao e codicada por uma tupla de 4 numeros naturais. Vimos na
introduc~ao como codicar um par de numeros naturais por um numero natural e, por extens~ao, podemos
codicar 4 numeros naturais com um numero natural.
O esquema de codagem das instruc~oes da MAR e:
Captulo 3. Func~oes Parciais Recursivas
18
codicado como h1; i; j; 0i
codicado como h2; i; j; 0i
codicado como h3; i; 1; 0i
codicado como h4; i; j; ki
codicado como h5; i; j; ki
Se x e a codicac~ao de uma tupla de quatro numeros naturais. Seja x a codicac~ao de uma instruc~ao
MAR, as func~oes seguintes permitem respeitivamente de calcular o tipo, o rotulo, o registro referenciado,
e caso a instruc~ao for um JMP a destinac~ao do pulo:
tip(x) = (1; 4; x)
rot(x) = (2; 4; x)
reg(x) = (3; 4; x)
des(x) = (4; 4; x)
Portanto, existe uma func~ao parcial recursiva inst : IN ! IN tal que inst(x) = 1 so se x e o codigo de
uma instruc~ao:
8x : IN inst(x) = 1 ,
(1 tip(x) 5)
^ (reg(x) 1)
^ (tip(x) 3 ) des(x) = 0)
^ (tip(x) = 3 ) reg(x) = 1):
Exerccio: Mostrar que inst e uma func~ao parcial recursiva.
P e um programa MAR compostos das 5 instruc~oes basicas: I1 ; : : : In . Seja P^ a codicac~ao do
programa P , I^j a codicac~ao da instruc~ao Ij :
P^ = hn; I^1 ; : : : I^n i
Ni
Ni
Ni
Ni
Ni
INC Rj
DEC Rj
CONTINUE
Rj JMP Rk a
Rj JMP Rk b
Seja x a codicac~ao de um programa MAR, as func~oes seguintes permitem respeitivamente de calcular
o numero de instruc~oes, o programa e as instruc~oes individuais do programa P tal que P^ = x:
num(x) = (1; 2; x)
pro(x) = (2; 2; x)
lin(x; i) = (i; num(x); pro(x))
Portanto, existe uma func~ao parcial recursiva prog : IN ! IN tal que prog(x) = 1 so se x e o codigo
de um programa legal. Informalmente, x e legal se cada linha do programa e uma instruc~ao legal, se a
ultima instruc~ao do programa e um CONTINUE e toda destinac~ao de um pulo e o rotulo de uma instruc~ao
do programa. Formalmente:
8x : IN prog(x) = 1 ,
8i : IN j 1 i num(x) inst(lin(x; i)) = 1
^ tip(lin(x; num(x))) = 3
^ 8i : IN j 1 i num(x)
tip(lin(x; i)) 2 f4; 5g )
9j : IN j 1 j num(x) rot(lin(x; j )) = des(lin(x; i))
Exerccio: Mostrar que inst e uma func~ao parcial recursiva.
Em conclus~ao, existe uma lista P0 ; P1 de todos os programas MAR, tal que P^i = i. Se prog(i) = 1,
ent~ao P^i e um programa MAR legal, sen~ao e ilegal.
Enm, para simular a execuc~ao de um programa MAR por uma func~ao parcial recursiva, e preciso
tambem codicar o conteudo dos registros. O programa MAR P n~ao faca refer^encia a nenhum registro
Ri tal que i > n e a codicac~ao do conteudo dos registros e
hr1 ; : : : rn ; 0i
Captulo 3. Func~oes Parciais Recursivas
19
Um limite superior de n e dado por a propriedade seguinte que pode ser provada a partir da denic~ao da
func~ao h; i:
8i : IN x prog(x) lin(i; x) reg(lin(i; x))
3.4.3 Simulac~ao da Execuc~ao de Programas MAR
O objetivo deste paragrafo e denir uma funca~o parcial recursiva univ , que tem como par^ametros a
codicac~ao x de um programa MAR P e a codicac~ao y do conteudo inicial dos registros, e que
e indenida se x n~ao e uma codicaca~o valida de um programa MAR,
e indenida se a execuc~ao de P n~ao termina se o registro R1 for inicializado com o valor y.
caso contrario, e denida e tem como valor a codicac~ao do conteudo do registro R1 quando termina
a execuc~ao de P , com a MAR inicializada com o valor y no registro R1.
Vamos tratar unicamente do caso de programa com um par^ametro. O caso de programas com varios
par^ametros e equivalente, pois vimos que existe uma func~ao de codicac~ao com um unico numero natural
qualquer numero nito de numeros naturais. Alem disso essa func~ao pode ser programada para ser
executada pela a MAR. Portanto uma func~ao com n par^ametros pode ser programado pela composic~ao
do programa de codicac~ao e de um programa de um par^ametro.
Proposic~ao 3.4 Seja P um programa MAR qualquer com 1 par^ametro. A func~ao comp : IN3 ! IN tal
que, se x = P^ , y e o valor inicial do registro R1, m o numero de instruc~oes executas, ent~ao comp(x; y; m) =
hi; z i onde
i e o numero da proxima instruc~ao a ser executada pela MAR,
z e a codicac~ao do conteudo dos registros da MAR usados por P .
e uma func~ao parcial recursiva.
Prova:
A prova da proposic~ao 3.4 necessita do lema seguinte:
Lema 3.1 Seja P um programa MAR qualquer, x = P^ , e i tal que 1 i Ln(x). Se y e a codicac~ao
do conteudo dos registros antes de executar a i-esima instruc~ao do programa P , ent~ao
proxlin(i; x; y) e o numero da proxima instruca~o executada,
proxcon(i; x; y) e a codicaca~o do conteudo dos registros,
depois de executar a i-esima instruc~ao. As func~oes proxline proxcons~ao parciais recursivas.
Uma prova intuitiva desse lema e dada em seguida. comp pode ser denido por composic~ao e recurs~ao
primitiva a partir das func~oes parciais recursivas de projec~ao , de codicac~ao h; i, e das func~oes proxline
proxcon:
comp(x; y; 0) = h1; yi
comp(x; y; m + 1) = h proxlin(1 (comp(x; y; m)); x; 2 (comp(x; y; m)))
proxcon(1 (comp(x; y; m)); x; 2 (comp(x; y; m)))i
Prova:
(Lema 3.1)
N
Captulo 3. Func~oes Parciais Recursivas
20
proxlin Se a i-esima instruc~ao n~ao e uma instruc~ao JMP, a proxima instruc~ao e a seguinte e proxlin(i; x; y) =
i + 1, o que e parcial recursivo.
Sup~oe agora que lin(x; i) seja a codicac~ao de uma instruc~ao JMP: tip(lin(x; i)) 2 f4; 5g. O numero
do registro testado pela instruc~ao e reg(lin(x; i)). O conteudo deste registro e (reg(lin(x; i)); x; y). Se
esse valor e diferente de 0 ent~ao, de novo, proxlin(x; i; y) = i + 1. Se for 0, ent~ao o pulo pode ser para
acima, ou para baixo. Se o pulo for para acima, ent~ao, a a posic~ao da instruc~ao alvo do pulo e dada pelo
maximo numero k tal que k i e rot(lin(x; k) = des(lin(x; i)). Se o pulo for para baixo, a posic~ao da
instruc~ao alvo e dada pelo mnimo numero k tal que k inum(x) e rot(lin(x; k) = des(lin(x; i)).
Nota o valor de proxlin aplicada a ultima instruc~ao do programa retorna um valor maior que o numero
num(x) de instruc~oes do programa.
Exerccio: Denir formalmente proxlin.
proxcon Para denir a func~ao proxcon, precisa se de duas func~oes auxiliares Ad; Sb : IN3 ! IN, tais
que, se y representa a codicac~ao de ate n registros, Ad(i; n; y) e Sb(i; n; y) t^em como valor a codicac~ao
do conteudo dos registros depois de respeitivamente incrementar e decrementar o i-esimo registro.
Sb(i; n; y) e o menor numero z , tal que z y e (i; n; z ) = (i; n; y);_ 1 e para todo k n, se k 6= i
ent~ao (k; n; y) = (i; n; y).
O caso de Ad e um pouco mais complicado. y e a codicac~ao de um grupo de, no maximo n registros.
Portanto, y e maior que o conteudo de qualquer um desses registros, y + 1 e maior que o conteudo de
qualquer registro depois de uma incrementac~ao. Ent~ao o numero pela codicac~ao de uma tupla de n
vezes y + 1 e um limite superior do conteudo de qualquer registro.
LS = h|y + 1; {z
: : : y + 1}i
n vezes
Ad(i; n; y) e o menor numero z , tal que z LS e (i; n; z ) = (i; n; y) + 1 e para todo k x, se k 6= i
ent~ao (k; n; y) = (i; n; y).
A denic~ao de proxcon e:
8
< Ad(reg(lin(x; i)); x; y) se tip(lin(x; i)) = 1
proxcon(i; x; y) = : Sb(reg(lin(x; i)); x; y) se tip(lin(x; i)) = 2
y
se tip(lin(x; i)) 3
N
Para denir a simulac~ao falta denir a codicac~ao do conteudo inicial dos registros. Como so consideramos programas com um par^ametro y, essa codicac~ao e dada por hy; 0i. Falta tambem denir quantos
passos de simulac~ao s~ao necessarios. Como um programa P pode n~ao terminar, o numero de passos
necessarios sera dado por uma funca~o parcial recursiva:
passos(x; y) = (m) [1 (comp(x; y; m)) = num(x)]
O resultado de rodar o programa P , de codicac~ao x, com o par^ametro y, e dado por:
(x; y) = 1 (2 (comp(x; hy; 0i; Passos(x; hy; 0i))))
Finalmente, devemos tratar o caso onde x n~ao e uma codicac~ao valida de programa MAR.
(x; y)
se pro(x)
univ =
indenido sen~ao
Teorema 3.1 Toda func~ao computavel pela MAR e parcial recursiva.
Prova:
Seja f uma func~ao computavel pela MAR. Por denic~ao, existe um programa P calculando f . Seja
N
x = P^ . Logo 8y f (y) = univ (x; y), portanto f e parcial recursiva.
Captulo 3. Func~oes Parciais Recursivas
21
Programa MAR universal
Ja mostramos que cada func~ao parcial recursiva e computavel pela MAR. Ent~ao existe um programa
Puniv que calcula univ . Esse programa e chamado universal, pois ele calcula o resultado de executar
qualquer programa MAR P para qualquer valor de entrada y. Em conclus~ao o programa Puniv e um
programa que simula a propria MAR.
3.5 A tese de Church
Lembramos a noc~ao intuitiva de o que e uma func~ao efetivamente computavel:
Denic~ao 3.5 (Func~oes efetivamente computaveis) Uma func~ao e efetivamente computavel se existe um algoritmo ou qualquer outro procedimento efetivo que permite calcular essa func~ao.
Isso signica que existe algum metodo que calcula, em um numero nito de passos, o valor da func~ao
quando ela e denida.
A tese de Church, ou tese de Church-Turing, e:
A classe das funco~es efetivamente computaveis e igual a classe das func~oes MAR-computaveis.
A tese de Church n~ao e um teorema. Isso quer dizer que n~ao e possvel provar-la, pois ela depende
do que s~ao exatamente funco~es efetivamente computaveis, o que n~ao pode ser denido exatamente. Para
justicar, de um ponto de visto cientco, o uso da tese de Church para provar outros resultados, podemos
observar que, em fsica, temos leis, como a lei de Newton, ou lei da gravidade, a partir das quais s~ao
desenvolvidas teorias, calculos, etc. A tese de Church pode ser considerado um axioma da teoria da
computac~ao.
Evidentemente, para n~ao desenvolver uma teoria inutil, esse axioma tem que corresponder a uma
certa realidade. O que podemos observar na realidade que justica a tese de Church ? Varios modelos
de computac~ao ja foram propostos, dentre dos quais a MAR, e as func~oes parciais recursivas. Ja vimos
o isomorsmo entre esses dois modelos. Os outros modelos de computac~ao, como Maquinas de Turing,
Sistemas de Post, foram propostos e calculam tambem a mesma classe de func~oes. Ate hoje ninguem
achou uma func~ao efetivamente computavel, que n~ao seja na classe das func~oes computaveis por esses
modelos de computac~ao.
3.5.1 Provas com a tese de Church
Sup~oe que disposemos de uma descric~ao formal ou informal de um algoritmo para calcular uma func~ao
f , e que queremos mostrar que essa func~ao e MAR-computavel, ou uma func~ao parcial recursiva, ou
Turing-computavel.
Um primeiro metodo de prova e desenvolver um programa MAR, ou denir uma func~ao parcial
recursiva, que implementa esse algoritmo, e mostrar que ele realiza a func~ao desejada. Foi esse metodo
que usamos ate agora.
Um segundo metodo, chamado de prova pela tese de Church, e simplesmente dizer que, como existe
um procedimento efetivo que calcula essa func~ao, ent~ao, pela tese de Church, ela e MAR-computavel.
Exemplo: Seja P um programa MAR, e f uma func~ao tal que
f (x; y) =
1 se a computac~ao de P (x) leva menos que t passos,
0 sen~ao.
Um algoritmo informal para calcular f e: Seja (x; y), simular a computac~ao de P (x) durante, no maximo,
y passos. Se ate o y-esimo passo, a execuc~ao de P n~ao para (quer dizer, n~ao chega a ultima instruca~o
CONTINUE), ent~ao o valor e 0, sen~ao e 1.
Captulo 3. Func~oes Parciais Recursivas
22
Ent~ao, pela tese de Church, f e MAR-computavel.
Exerccio: Sup~oe que f seja uma func~ao total a um par^ametro. Provar, pela tese de Church, que a
func~ao h seguinte e MAR-computavel:
h(x) =
1 se x faz parte do domnio de chegada de f .
indenida sen~ao.
Exerccio: Mostrar, pela tese de Church, que a func~ao de Ackermann : IN2 ! IN e computavel:
(0; y) = y + 1;
(x + 1; 0) = (x; 1)
(x + 1; y + 1) = (x; (x + 1; y))
Exist^encia de func~ao n~ao-computavel
Repetimos agora um teorema apresentado na introduca~o deste curso.
Teorema 3.2 Existe uma func~ao total n~ao computavel.
Prova:
A prova usa o metodo da diagonal. P0 ; P1 ; : : : e o conjunto de todos os programas MAR possveis, e
0 ; 1 ; : : : as func~oes correspondentes. Pela tese de Church, todas as func~oes efetivamente computaveis
s~ao nesta lista. Seja f : IN ! IN tal que:
f (n) =
n (n) + 1 se (n) e denido
0 se (n) n~ao e denido
f e diferente de qualquer func~ao efetivamente computavel, portanto f nao e computavel.
N
Captulo 3. Func~oes Parciais Recursivas
N0
23
Rk+1
R1
R1
Rk+n
Rn
Rm
Rk+n+m
CLR Rk+n+m
:::
P1
:::
:::
Rk+n+1
R1
R1
Rk+1
CLR Rk
:::
Pg
Rn
Rk+n
CLR Rn+1
CONTINUE
:::
CLR Rk
P2
Rk+n+2
R1
R1 Rk+1
:::
Rn
Rk+n
CLR Rn+1
:::
CLR Rk
Pm
Rk+n+m
Rk+n+1
R1
Figura 3.2: Composic~ao de programas MAR
Rk+1
:::
N1
R1
Rk+n
Rn
CLR Rk+n+1
R1
Rk+1
:::
Rn
Rk+n
Rn+1
Rk+n+1
CLR Rn+2
:::
CLR Rk
Ph
N2
R1 JMP N2b
INC Rk+n+1
JMP N1a
R1
Rk+n+1
CONTINUE
Figura 3.3: Minimizac~ao de programas MAR