Filo

´ Logica y Computabilidad

Primer Cuatrimestre 2011

´ Practica 7 -Funciones no-computables y conjuntos c.e.Ejercicio 1. Probar, usando una diagonalizaci´n, que las siguientes funciones no son computables: o f1 (x, y) = f3 (#p, y, z) = 1 si Halt(x, y) 0 en otro caso 1 si Ψp (y) > z 0 en otro caso f2 (#p, y) = f4 (#p) = 1 si Ψp (y) = 0 0 en otro caso 1 si Ψp (#p) = #p 0 en otro casoEjercicio 2. Probar, reduciendo cualquier funci´n del Ejercicio 1, que las siguientes funciones no o son computables: g1 (x, y) = g3 (#p, y, z) = 1 si ¬Halt(y, x) 0 en otro caso z + 1 si Ψp (y) = z 0 en otro caso g2 (#p, #q, z, w) = g4 (#p, #q, z) = 1 si Ψp (z) > Ψq (w) 0 en otro caso (Ψp ◦ Ψq )(z) si Ψq (z)↓ y (Ψp ◦ Ψq )(z)↓ 0 en otro caso

Ejercicio 3. Probar que la siguiente funci´n no es computablereduciendo la funci´n f4 del Ej. 1. o o g3 (#p, y, z) = z 0 si Ψp (y) = z en otro caso

Sugerencia: Revisar que la reducci´n maneje correctamente el caso f4 (0). o Ejercicio 4. Decimos que una funci´n parcial computable f es extensible si existe g computable o tal que g(x) = f (x) para todo x ∈ dom f . Probar que existe una funci´n parcial computable que o no es extensible (Sugerencia:considerar una funci´n tal que para todo punto se pueda decidir si o fue extendida o no). Ejercicio 5. Dada una funcion f : Nn+1 → N y un n´mero k, llamamos aplicaci´n parcial del i-´siu o e mo par´metro a obtener una nueva funci´n g : Nn → N tal que g(x1 , . . . , xn ) = f (x1 , . . . , k, . . . , xn ) a o d´nde k aparece en el lugar del i-´simo par´metro. Por ejemplo a partir de la funci´n suma(x, y) oe a o se puede obtener incrementar(x) = suma(x, 1). a. Mostrar que dada una funci´n parcial computable f : Nn → N y un n´mero 1 ≤ i ≤ n existe o u una funci´n parcial computable fi (x1 , . . . , xi−1 , xi+1 , . . . , xn , xi ) = f (x1 , . . . , xn ), es decir, en o la cual el i-´simo par´metro se mueve hacia el final. e a b. Demostrar que, dada una funci´n parcial computable f : Nn → N y un n´mero1 ≤ i ≤ n existe o u una funci´n primitiva recursiva Af,i : N → N que toma un n´mero y devuelve un programa o u que computa a la funci´n resultante luego de aplicar el i-´simo par´metro. Es decir Af,i (k) = o e a #p implica Ψp (x1 , . . . , xi−1 , xi+1 , . . . , xn ) = f (x1 , . . . , xi−1 , k, xi+1 , . . . , xn ). Sugerencia: Usar el teorema del par´metro. a Ejercicio 6. Probar, reduciendocualquier funci´n del Ejercicio 1 y usando el teorema del par´meo a tro, que las siguientes funciones no son computables: g1 (x) = g3 (#p) = 1 0 13 0 si Halt(1337, x) en otro caso si Ψp = 7 en otro caso
(0)

g2 (#p, #q, z) = g4 (#p) =

1 si Ψp (z) > Ψq (z) 0 en otro caso 1 si 5 ∈ Dom Ψp 0 en otro caso
(1)

1

Ejercicio 7. Demostrar que existe un programa p tal que Ψp (x) ↓ si y s´lo si x =#p. o Ejercicio 8. Demostrar, usando el teorema de la recursi´n, que las siguientes funciones no son o computables: h1 (#p) = h3 (#p) = 1 si #p ∈ Im Ψp 0 en otro caso
(1) (1)

h2 (#p, y) = h4 (#p) =

1 si Ψp (y) > #p 0 en otro caso 1 0 si | Dom Ψp | = #p en otro caso
(1)

1 si Im Ψp es infinita 0 en otro caso

Ejercicio 9. Sean C1 , . . . , Ck conjuntos de ´ ındices de programas y sea D =C1 ∩ . . . ∩ Ck . a. Demostrar que D es un conjunto de ´ ındices de programas. b. Proponer un conjunto, que no sea un conjunto de ´ ındices de programas y no sea computable. Ejercicio 10. Probar que son equivalentes i. D es un conjunto de ´ ındices de programas (D = {#p : Ψp ∈ C}, con C una clase de funciones). ii. Para todo par de programas p y q, si #p ∈ D y Ψp = Ψq entonces #q ∈ D. Ejercicio 11.Demostrar, usando reducciones y el teorema de Rice, que las siguientes funciones no son computables: g1 (#p) = g3 ( #p, y ) = 1 0 1 0 si Dom Ψp = ∅ en otro caso si y ∈ Dom Ψp en otro caso
(1) (1)

g2 (#p, #q) = g4 ( #p, #q ) =

1 si Dom Ψp ∪ Dom Ψq 0 en otro caso Ψp (Ψq (72)) 73
(1)

(1)

(1)

=N

si Ψp ◦ Ψq es total en otro caso

(1)

Observaci´n: Notar que la composici´n de...