1)

Considérese la función f(x,y) que se define a continuación:

donde la función pegar(z,x) añade como primer elemento (es decir, por la izquierda) el valor x al vector codificado en el número de Gödel z.

a) ¿Se hace un uso apropiado de la función resta en esta definición? Justificar la respuesta.

b) Describe con tus palabras el cómputo realizado por esta función.

c) Demostrar que esta función es WHILE-calculable (utilizar notación extendida de WHILE).

Dado un número natural n demostrar que es m-REC la función que devuelve el número de Gödel del vector formado por todos los divisores de n.

Se puede hacer uso de la función pegar(z,x), descrita en el problema 1 y de todas las definidas en clase.

Dada la siguiente función:

demostrar que es m-recursiva haciendo uso de las funciones que realiza la suma de x e y, y que es la función asociada (o característica) del predicado “ser x mayor que y”.

Dado un número natural N, que representa la godelización de un vector de naturales, demostrar que la siguiente función es WHILE-calculable:

para ello se puede hacer uso de los programas WHILE: , que calcula el número de Cantor de un par de números naturales, y y que devuelven la primera y segunda componentes de un número de Cantor. Se puede utilizar la notación extendida de WHILE.

Dados w y z, números de Cantor que codifican vectores de n elementos, demostrar que es m-recursiva la función barajar(w,z). Esta función tiene como entrada 2 números de Cantor y devuelve el número de Cantor que codifica al vector resultante de mezclar los 2 de entrada, de forma que el primer elemento del vector resultante es el primer elemento de w, el segundo es el primero de z, el tercero es el segundo de w, y así hasta completar los 2n elementos.

Se podrá hacer uso de la función que calcula el número de Cantor de un par de números naturales.

Nota: un árbol binario completo es aquel al que no le falta ninguna rama hasta un nivel de profundidad dado.

Se podrá hacer uso de la función que calcula el número de Cantor de un par de números naturales, la función extraer(z,k) que devuelve el elemento k-ésimo del vector codificado en el número de Cántor z, raiz2(x) que devuelve la raiz cuadrada de x y par(x) que decide si x es par (devuelve 1 si lo es y 0 si no lo es).

Nota: para demostrar que es m-recursiva no se puede aportar un programa WHILE y exponer el Teorema de Equivalencia.

Definimos la función filtro(t,V) del siguiente modo:

Dados un tÎN y VÎN, siendo V la godelización de un vector ÎNⁿ, la función devuelve un número que representa la godelización de todos los v_i<t, en el mismo orden en que se encuentran en V.

Ejemplo:

filtro(1,V)=F

V: godelización de {1,6,2,0,3}

F: godelización de {6,2,3}

Si el resultado fuese la godelización de 6, 2 y 3, en cualquier otro orden, no sería correcto.

Demostrar que la función filtro Î F(WHILE).

Demostrar que la función filtro Î PRIM.

Siendo V un vector con un número par de elementos, z es el número que resulta de codificar V de acuerdo con la figura.

método: generar un vector que tenga como último elemento la cantorización del primero y último, como penúltimo la cantorización del segundo y penúltimo, y así hasta completar todos los elementos del vector original, a continuación cantorizar el vector resultante.

1) Demostrar que es REC la función ACantor(z) que recibe un número según el esquema anterior y devuelve el número de Cantor del vector V contenido en z.

2) Demostrar que es REC la función Hay3(z) que recibe un número según el esquema anterior y devuelve 1 si existe un elemento con el valor 3 en el vector V contenido en z y 0 en caso contrario.

Se podrá hacer uso de todas las funciones de Cantor expuestas durante el curso y de las funciones aritméticas más conocidas (suma, resta, potencia, raíz, etc.).