UNIVERSIDADE da MADEIRA
Departamento de Matemática e Engenharias
TEORIA DA COMPUTABILIDADE E COMPLEXIDADE
Licenciaturas em Engenharia Informática, Ensino de Informática e
Matemática
o
1 Semestre 2005/2006
Folha de exercı́cios no 12
Teorema s-m-n. Programas Universais
1. Considere a função
g(x) =
x
, se x é múltiplo de n
,
indefinida , caso contrário
com n ∈ N0 . Mostre que existe uma função total computável k, tal que:
• φk(n) (x) ≃ g(x)
• Wk(n) = Ek(n) = nN0
2. Mostre que existe uma função total computável k tal que, para cada n ∈ N0 , k(n)
é um ı́ndice da seguinte função unária:
√
n
x
, se x é uma potência perfeita de ordem n
f (x) =
indefinida , caso contrário
3. Mostre que existe uma função total computável k tal que, para cada n ∈ N0 , Wk(n) é
o conjunto de potências perfeitas de ordem n. (Por exemplo: Wk(2) = {0, 1, 4, 9, . . .})
4. Mostre que existe uma função total computável h tal que, para cada n ∈ N0 , Eh(n) é o
conjunto de potências perfeitas de ordem n. (Por exemplo: Eh(3) = {0, 1, 8, 27, . . .})
5. Seja n ≥ 1. Mostre que existe uma função total computável s tal que
(n)
Ws(x) = {(y1 , . . . , yn ) ∈ Nn0 : y1 + · · · + yn = x}
1
6. Recordando que o predicado S1 (e, x, y, t) ≡ “Pe (x) y em t ou menos passos” é
decidı́vel:
(a) Mostre que existe um predicado decidı́vel Q(x, y, z) tal que:
i. y ∈ Ex se e só se ∃z : Q(x, y, z),
ii. se y ∈ Ex e Q(x, y, z), então φx ((z)1 ) = y.
(b) Deduza que existe uma função computável g(x, y) tal que:
i. g(x, y) está definida se e só se y ∈ Ex ,
ii. se y ∈ Ex , então g(x, y) ∈ Wx e φx (g(x, y)) = y; i.e. g(x, y) ∈ φ−1
x ({y}).
7. Mostre que existe uma função total computável g tal que, para qualquer x ∈ N0 , se
tem φg(x) = (φx )2 .
8. Mostre que existe uma função total computável s(x, y) tal que Ws(x,y) = Wx ∪ Wy .
9. Mostre que existe uma função total computável k(x) tal que, para todo o x ∈ N0 ,
Ek(x) = Wx .
10. Mostre que existe uma função total computável s(x, y) tal que, para quaisquer
x, y ∈ N0 , Es(x,y) = Ex ∪ Ey .
2