Date post: | 13-Oct-2018 |
Category: |
Documents |
Upload: | vuongtuyen |
View: | 215 times |
Download: | 0 times |
Tema 5:Procedimientos para obtener funciones
computables
Dpto. Ciencias de la Computacion e Inteligencia ArtificialUniversidad de Sevilla
Logica y ComputabilidadCurso 2010–11
LC, 2010–11 Procedimientos para obtener funciones computables 5.1
Procedimientos de definicion y funcionesbasicas
I Estudiaremos procedimientos para definir funciones que nospermitan obtener nuevas funciones computables, a partir deotras funciones computables ya conocidas.
I Es deseable que estos procedimientos de definicion permitanobtener todas las funciones GOTO–computables a partir dealgunas funciones basicas cuya computabilidad seaindiscutible.
I Esto nos proporcionara, mas adelante, una caracterizacion delas funciones GOTO-computables independiente de todomodelo de computacion particular.
I Consideramos tres procedimientos basicos:I Composicion.I Recursion primitiva.I µ–Recursion (o Minimizacion).
LC, 2010–11 Procedimientos para obtener funciones computables 5.2
Composicion
I Dadas g : Nn− −→ N, h1, .., hn : Nm− −→ N, decimos que fes la composicion de g y h1, . . . , hn, si
Para todo ~x ∈ Nm, f (~x) = g(h1(~x), . . . , hn(~x))
I Usamos como notacion f = C(g ; h1, . . . , hn).I Lema. GCOMP es cerrado bajo composicion:
I En efecto, el siguiente programa calcula f = C(g ; h1, ..., hn):
Z1 ←− h1(X1, ...,Xm)...
Zn ←− hn(X1, ...,Xm)Y ←− g(Z1, ...,Zn)
I Lema. El conjunto de funciones totales es cerrado bajocomposicion.
LC, 2010–11 Procedimientos para obtener funciones computables 5.3
Recursion Primitiva(I)
I Dadas g : Nm− −→ N, h : Nm+2− −→ N, decimos quef : Nm+1− −→ N se define por recursion primitiva a partir deg y h (y escribimos f = R(g , h)), si
Para todo ~x ∈ Nm, y ∈ N{
f (~x , 0) = g(~x)f (~x , y + 1) = h(~x , y , f (~x , y))
I Esta definicion se extiende al caso m = 0:{f (0) = kf (x + 1) = h(x , f (x))
donde k ∈ N. En este caso escribimos: f = R(k, h), ydiremos que f se obtiene por recursion primitiva a partir de laconstante k y de h.
LC, 2010–11 Procedimientos para obtener funciones computables 5.4
Recursion Primitiva(II)
I Lema. GCOMP es cerrado bajo recursion primitiva:
I En efecto, sean g : Nm− −→ N, h : Nm+2− −→ NG-computables.El siguiente programa calcula f = R(g ; h):
Y ←− g(X1, ...,Xm)[A] IF Xm+1 = 0 GOTO E
Y ←− h(X1, ...,Xm,Z ,Y )Z ←− Z + 1Xm+1 ←− Xm+1 − 1GOTO A
I Lema. El conjunto de funciones totales es cerrado porrecursion primitiva.
LC, 2010–11 Procedimientos para obtener funciones computables 5.5
µ–Recursion (I)
I Sea f : Nn+1− −→ N, (n ≥ 1). La funcion definida porµ–recursion a partir de f es la funcion fµ : Nn− −→ N dadapor
fµ(~x) =
{min{y : f (~x , y) = 0 ∧ ∀z < y (f (~x , z) ↓)} si existe↑ e.o.c .
I Nota. Usualmente escribiremos: µy(f (~x , y) = 0).
I Lema. GCOMP es cerrada bajo µ–Recursion.
I En efecto, sea f : Nn+1− −→ N, (n ≥ 1), GOTO–computable.
El siguiente programa calcula fµ:
[A] Z ←− f (X1, ...,Xn,Y )IF Z = 0 GOTO EY ←− Y + 1GOTO A
LC, 2010–11 Procedimientos para obtener funciones computables 5.6
µ–Recursion (II)
Para los predicados suele darse una definicion ligeramente distinta:
I Si θ es un predicado n + 1-ario, definimos:
θµ(~x) ≡ µy(θ(~x , y)) =
{min{y : θ(~x , y)} si existe el mınimo↑ e.c.o.c.
I Lema. θ ∈ GCOMP =⇒ µy(θ(~x , y)) ∈ GCOMP
I Observacion: La µ–Recursion no proporciona siemprefunciones totales.
I Ejemplo. Sea θ el siguiente predicado de aridad 2:
θ(x , y) =
{1 si x = 00 e.o.c.
Entonces, θµ(x) = µy(θ(x , y)) =
{0 si x = 0↑ si x 6= 0
Como θ es computable, la funcion θµ es computable.
LC, 2010–11 Procedimientos para obtener funciones computables 5.7
Funciones basicas
Llamaremos funciones basicas a las siguientes funciones:
I Siguiente: S : N −→ N; S(x) = x + 1
I Identicamente nula: O : N −→ N; O(x) = 0
I Proyecciones: Para cada i , n ∈ N (1 ≤ i ≤ n),∏ni : N −→ N;
∏ni (x1, . . . , xn) = xi
Lema. Las funciones basicas son G-computables:
I Siguiente, S :
{X ←− X + 1Y ←− X
I Nula, O : Programa vacıo, p∅
I Proyecciones,∏(n)
j : Y ←− Xj
LC, 2010–11 Procedimientos para obtener funciones computables 5.8
Ejemplos-I- (Composicion y Recursion)
Las siguientes funciones son GOTO-computables y totales:
I Identidad IN : N −→ NI Constantes: C k
a : Nk −→ N, C ka (~x) = a (a, k ∈ N, k > 0)
I Predecesor: pr : N −→ N
pr(x) =
{0 si x = 0
x − 1 si x > 0
I Diferencia reducida:•− : N2 −→ N
x•− y =
{0 si x ≤ y
x − y e.c .o.c .
I Signo: sg : N −→ N
sg(x) =
{0 si x = 01 e.c.o.c .
LC, 2010–11 Procedimientos para obtener funciones computables 5.9
Ejemplos-II- (Composicion y Recursion)
I Signo inverso:−sg : N −→ N
−sg (x) = 1
•− sg(x)
I Suma: + : N2 −→ N
+(x , y) = x + y
I Producto: · : N2 −→ N
·(x , y) = x ·y
I Mınimo: min : N2 −→ N y Maximo: max : N2 −→ N.
min(x , y) =
{x si x ≤ yy e.c .o.c .
max(x , y) =
{x si x ≥ yy e.c.o.c .
LC, 2010–11 Procedimientos para obtener funciones computables 5.10
Ejemplos-III- (Composicion y Recursion)
I Distancia: || : N2 −→ N
|x − y | =
{x − y si x ≥ yy − x e.c .o.c .
I Exponencial: exp : N2 −→ N
exp(x , y) =
{1 si x = 0 ∧ y = 0xy e.c .o.c.
I Factorial: fact : N −→ N
fact(x) =
1 si x = 0∏1≤j≤x
j e.c .o.c .
LC, 2010–11 Procedimientos para obtener funciones computables 5.11
Ejemplos-IV- (µ–Recursion)
I Minimizacion de la suma: Sum(x , y) = x + y
Sumµ(x) = µy(Sum(x , y) = 0) =
{0 si x = 0↑ e.o.c.
I Minimizacion de la funcion g(x , y) =
{x·− y si y ≤ x↑ si y > x
gµ(x) = Id(x)
I La funcion funcion raız cuadrada parcial, Sqrt, definida ası:
Sqrt(x) =
{y si existe y ∈ N tal que y 2 = x↑ e.o.c
es GOTO-computable.En efecto, Sqrt(x) = µy(|x − y 2| = 0)
LC, 2010–11 Procedimientos para obtener funciones computables 5.12
Predicados y conjuntos GOTO–computables.
I Un predicado sobre N es GOTO–computable si la funcionque lo define es GOTO–computable.
I Un conjunto A ⊆ Nk es GOTO–computable si su funcioncaracterıstica, CA, es GOTO–computable.
Ejemplos:
I Los conjuntos ∅ y Nk , para cada k ∈ N sonGOTO–computables.
I Los predicados: θ1(x , y) ≡ x = y ; θ2(x , y) ≡ x ≤ y ;θ3(x , y) ≡ x < y son GOTO–computables.
I Si f : Nk −→ N es GOTO–computable , entonces lospredicados (k + 1)-arios siguientes son GOTO–computables:
θ(~x , y) ≡ f (~x) = y ; θ′(~x , y) ≡ f (~x) ≤ y ; θ′′(~x , y) ≡ f (~x) < y .
I El grafo G (f ) = {(~x , y) ∈ Nk+1 : f (~x) = y} de una funcionf : Nk −→ N, GOTO–computable, es GOTO–computable.
LC, 2010–11 Procedimientos para obtener funciones computables 5.13
Operaciones con conjuntos y predicados
I Proposicion. Sean θ, θ′ predicados sobre N, k–arios yGOTO–computables, entonces los predicados:¬θ, θ ∧ θ′, θ ∨ θ′, θ ⇒ θ′ y θ ⇔ θ′
son predicados GOTO-computables.
I ¬θ(~x) = sg(θ(~x))I (θ ∧ θ′)(~x) = θ(~x)·θ′(~x)I (θ ∨ θ′)(~x) = sg(θ(~x) + θ′(~x))I θ ⇒ θ′ ≡ ¬θ ∨ θ′I θ ⇔ θ′ ≡ θ ⇒ θ′ ∧ θ′ ⇒ θ
I Corolario. Si A,B ⊆ Nk son conjuntos GOTO-computables,entonces: Nk − A; A ∩ B; A ∪ B son GOTO-computables.
I CNk−A = ¬CA;I CA∩B = CA ∧ CB ;I CA∪B = CA ∨ CB
LC, 2010–11 Procedimientos para obtener funciones computables 5.14
Definiciones por casos
Proposicion. Sean k ≥ 2 y f1, . . . , fk : Nm −→ N funcionesGOTO-computables y totales. Sea {A1, . . . ,Ak} una particion deNm en conjuntos GOTO-computables, es decir,
Nm =⋃k
i=1 Ai , ∀i(Ai 6= ∅), y ∀i , j = 1, . . . , k , i 6= j ⇒ Ai∩Aj = ∅
Entonces, la funcion g : Nm −→ N definida por
g(~x) =
f1(~x) si ~x ∈ A1
......
...fk(~x) si ~x ∈ Ak
es GOTO-computable y total.
I Pues g = f1·CA1 + . . .+ fk ·CAkes GOTO-computable.
I Nota: La proposicion anterior puede expresarse con predicados
GOTO-computables, θ1, . . . , θk , que sean exhaustivos y excluyentes.
LC, 2010–11 Procedimientos para obtener funciones computables 5.15
Minimizacion acotada -I-
Definicion. Sea θ(~x , y) un predicado (n + 1)–ario. Definimos lafuncion total θ∗µ : Nn+1 → N, ası:
θ∗µ(~x , y) =
{min{z ≤ y : θ(~x , z)} si existe tal mınimoy + 1 e.c.o.c.
I Usualmente escribiremos: µz ≤ y θ(~x , z)y diremos que θ∗µ se obtiene de θ por minimizacion acotada.
Proposicion. Si θ ∈ GCOMP(n+1) entonces θ∗µ ∈ GCOMP(n+1).
I Es facil disenar un programa que calcule θ∗µ(~x , y) (Ejercicio).
LC, 2010–11 Procedimientos para obtener funciones computables 5.16
Minimizacion acotada -II-
I Definicion. Sea f (~x , y) una funcion (n + 1)–aria y total.Definimos la funcion de aridad n + 1, f ∗µ , ası:
f ∗µ (~x , y) = µz ≤ y (f (~x , z) = 0)
I Diremos que f ∗µ se obtiene de f por minimizacion acotada.
I Proposicion. Si f ∈ GCOMP(n+1) y total entoncesf ∗µ ∈ GCOMP(n+1).
I Ejemplos.I La funcion cociente.
qt(x , y) =
{0 si y = 0µt ≤ x (x < (t + 1) · y) e.o.c.
I La funcion resto.
rm(x , y) =
{x•− (y · qt(x , y)) si y 6= 0
0 si y = 0
LC, 2010–11 Procedimientos para obtener funciones computables 5.17
Cuantificacion acotada
I Proposicion. Sea θ ∈ G -COMP(n+1) un predicado n + 1-ario.Los siguientes predicados son GOTO-computables:
θ1(~x , y) ≡ ∃z ≤ y θ(~x , z); θ2(~x , y) ≡ ∀z ≤ y θ(~x , z)
I En efecto:I θ1(~x , y) = sg(y + 1
•− µt ≤ y(θ(~x , t)))
I θ2(~x , y) = sg(y + 1•− µt ≤ y(¬θ(~x , t)))
I Ejemplos. Los siguientes predicados son GOTO-computables:
I Predicado de divisibilidad, x |y :
θ(x , y) ≡ ∃z ≤ y(y = z · x)
I Predicado de primalidad:
primo(x) ≡ (x > 1) ∧ ∀t ≤ x((t|x)→ (t = 1 ∨ t = x))
LC, 2010–11 Procedimientos para obtener funciones computables 5.18
La sucesion de los numeros primos
I Es la funcion p : N→ N definida por:
I p(0) = 0, yI para todo n ≥ 1, p(n) = pn es el n–esimo primo.
I p es GOTO–computable ya que se define por recursion ası:{p(0) = 0p(x + 1) = µy (primo(y) ∧ y > p(x))
LC, 2010–11 Procedimientos para obtener funciones computables 5.19
Codificacion de sucesiones
Definicion (Sucesiones finitas). Una codificacion de Nm
a partir de N, es una funcion total f : Nm −→ N que verifica:
1. f es GOTO–computable e inyectiva.
2. Para cada i , 1 ≤ i ≤ m, la funcion total, gi : N −→ N:
gi (x) =
{ai si x ∈ rang(f ) ∧ x = f (a1, ..., am)0 e.c .o.c.
es GOTO–computable.
Definicion (Sucesiones de longitud arbitraria).Sea N′ = {ε} ∪ N ∪ N2 ∪ ... ∪ Nk ∪ ... (donde ε es la sucesionvacıa -de longitud 0-).Una funcion f : N′ −→ N, codifica N′ a partir de N, si:
I f es total.
I ∀j ≥ 1, f � Nj es una codificacion de Nj , a partir de N.
LC, 2010–11 Procedimientos para obtener funciones computables 5.20
La funcion par
I Es la funcion total 〈· , ·〉 : N2 −→ N definida por
〈x , y〉 = 2x · (2y + 1)•− 1
I La funcion par es GOTO-computable y biyectiva.I Para todo x , y ∈ N se verifica: x ≤ 〈x , y〉, y ≤ 〈x , y〉.I Existen l , r : N −→ N tales que si z = 〈x , y〉 ,
l(z) = x ; r(z) = y z = 〈l(z), r(z)〉
l y r son funciones decodificadoras de 〈 ·, ·〉.I Las funciones l , r son GOTO-computables y totales.
I Usando la funcion par podemos codificar N3 a partir de N:
(x , y , z) −→ 〈x , 〈y , z〉〉
Y, en general, Nk a partir de N.
LC, 2010–11 Procedimientos para obtener funciones computables 5.21
Numeros de Godel
Sea {pn : n ≥ 1} la sucesion de numeros primos y [ · · · ] : N′ −→ Nla funcion definida ası:{
[ε] = 1[a1, ..., an] = pa1
1 ...pann
Diremos que [a1, ..., an] es el numero de Godel de la sucesionfinita a1, ..., an.
Propiedades:
I La funcion [ · · · ] codifica N′ a partir de N.
I Para todo i , 1 ≤ i ≤ n se verifica: ai ≤ [a1, ..., an].
I La funcion [ · · · ] no es inyectiva.
I rang( [ · · · ])= N− {0}.I Cada numero natural codifica infinitas sucesiones.
LC, 2010–11 Procedimientos para obtener funciones computables 5.22
Las funciones componente y longitud
I Lema. Si x ∈ N− {0, 1} existen unos unicosa1, ..., an ∈ N, an 6= 0, tales que x = [a1, ..., an].
I Escribiremos (x)i = ai si i ∈ {1, ..., n} y diremos que ai esla componente i–esima de x .
I Si i /∈ {1, ..., n} entonces escribiremos: (x)i = 0.
I Definicion. Denominaremos funcion componente a lafuncion: ( · ) : N2 −→ N , definida ası:
(x)i =
{0 si x = 0
µt ≤ x (¬(pt+1i |x)) e.c.o.
I La funcion componente es GOTO–computable y total.
I Definicion. Definimos la funcion longitud, long : N −→ N,ası:
long(x) = µi ≤ x ((x)i 6= 0 ∧ ∀j ≤ x (j > i → (x)j = 0))
I La funcion longitud es GOTO–computable y total.
LC, 2010–11 Procedimientos para obtener funciones computables 5.23