Siguiente: Funciones de apareamiento y Un nivel arriba: Funciones recursivas primitivas Anterior: Función de Ackermann

Segunda lista de ejercicios

1. Describa una función $F:\mbox{\it programas-{\bf while }'s}\rightarrow N$ que sea efectivamente una BIYECCION.

2. Códigos basados en primos: Consideremos a los primeros 7 números primos: 2, 3, 5, 7, 11, 13 y 17, y a la codificación de los elementos sintácticos de los programas-while 's $\lceil\cdot\rceil:\mbox{\it programas-{\bf while }'s}\rightarrow N$ construída como sigue: Representación de variables: A la variable Xw, donde $w\in \{0,1\}$ es una lista de 0's y 1's, la representamos por el número entero

$$r(Xw)=2^{\mbox{\it long}(w)}+(w)_2.$$

Codificación de instrucciones:

$$\begin{eqnarray*}{[Xw++]} &\mapsto& 17^{r(Xw)} \\ {[Xw--]} &\mapsto& 13^{r(Xw)... ...ace {\bf do }P}]} &\mapsto& 11^{r(Xw)}\cdot 7^{\lceil P\rceil} \end{eqnarray*}$$

Codificación de programas:

$$\begin{eqnarray*}{[\mbox{\it Inst};\mbox{\it Ruti}]} &\mapsto& 5^{\lceil\mbox{\i... ...{\mbox{\it Ruti}\}]} &\mapsto& 2^{\lceil\mbox{\it Ruti}\rceil} \end{eqnarray*}$$

a) Muestre que $\lceil\cdot\rceil$ es una función inyectiva. b) Describa a un procedimiento para calcular su inversa. c) Decida si acaso es una biyección.

3. Considerando a la codificación con primos del ejercicio anterior, describa un procedimiento para calcular los códigos de los numerales.

4. Los códigos basados en primos crecen (excesivamente) rápido. Considerando a la biyección de Cantor describa una codificación similar a la basada en primos con un (mucho) menor crecimiento.

5. Muestre que la función

$$\begin{array}{rcl} f:0 &\mapsto& 0 \\ 1 &\mapsto& 1 \\ 2... ...aci\'on consecutiva,} \\ \vdots &\vdots& \vdots \end{array}$$

es recursiva primitiva.

6. Muestre que la función

$$f:x \mapsto \left\{\begin{array}{ll} 2x &\mbox{\rm si $x$ es... ...fecto,} \\ 2x+1 &\mbox{\rm en otro caso,} \end{array}\right.$$

es recursiva primitiva.

7. Muestre que la función

$$\phi:x \mapsto \mbox{\rm card}\{y\leq x:y\vert x\}=(\mbox{\rm n\'umero de divisores de $x$}),$$

es recursiva primitiva. Tenemos, por ejemplo, que para $x=1995=3\cdot 5\cdot 7\cdot 19$,

$$\pi(1995)=16=2^4.$$

8. Muestre que la función

$$\sigma:x \mapsto \left\{\begin{array}{ll} 0 &\mbox{\rm si }x... ...\sum_{y\vert x} y &\mbox{\rm en otro caso,} \end{array}\right.$$

es recursiva primitiva. $\sigma(x)$ es la suma de divisores de x. Tenemos, por ejemplo, que para

$$x=1995=3\cdot 5\cdot 7\cdot 19,$$

$$\begin{eqnarray*}\sigma(1995) &=& 1+3+5+7+19+15+21+57+35+ 95+ 133+ \\ & & 105+ 285+ 399+ 665+ 1995 \\ &=& 3840. \end{eqnarray*}$$

9. Muestre que la función

$$\lfloor\sqrt{\cdot}\rceil:x \mapsto n,\mbox{\rm donde }n^2\leq x<(n+1)^2,$$

es recursiva primitiva.

10. Muestre que la función $f:N\rightarrow N$ tal que

$$\begin{eqnarray*}f(0) &=& 1, \\ f(1) &=& 4, \\ f(2) &=& 6, \\ f(x+3) &=& f(x)+f(x+1)^2+f(x+2)^3, \end{eqnarray*}$$

es recursiva primitiva.

11. Sea

$$u:n\mapsto \mbox{\rm el $n$-\'esimo entero que es suma de dos cuadrados,}$$

$$\begin{array}{rcl} u:0 &\mapsto& 0=0^2+0^2 \\ 1 &\mapsto& ... ...5 &\mapsto& 8=2^2+2^2 \\ \vdots &\vdots& \vdots \end{array}$$

Muestre que u es recursiva primitiva.

12. Muestre por doble inducción las propiedades siguientes: a) $\forall n>0: f_n(x,y)<f_n(x,y+1)$. b) $\forall n>0: f_n(x,y)<f_{n+1}(x,y+1)$.

13. Muestre que $\forall n:{\cal E}^2\subset {\cal E}^{n}$.

14. a) Describa un procedimiento para calcular la función exponenciación: $(n,x)\mapsto\left\{\begin{array}{ll} x^n &\mbox{\rm si $x\not=0$\space o $n\not=0$ , } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$. b) Describa un procedimiento más eficiente que el anterior para calcular a la exponenciación, o pruebe que el anterior no se puede mejorar. Sugerencia: Para calcular x³¹ calcule la sucesión

x, x²,x⁸,x¹⁶,x²⁴,x²⁸,x³⁰,x³¹.

15. Un número real $x\in [0,1]$ es computable si la función

$$\begin{eqnarray*}f_x:N &\rightarrow& [[0,9]] \\ n &\mapsto& \mbox{\rm\begin{mi... ...mo d\'\i gito en la expansi\'on decimal de $x$ ,\end{minipage}} \end{eqnarray*}$$

es computable. Muestre que todo número racional es computable.

16. Muestre que la raíz cuadrada de un número computable es computable.

17. Muestre mediante un argumento ``diagonal'' que existen números en el intervalo [0,1] que no son computables.

18. Muestre que $\pi$ es computable. Sugerencia: Puede utilizar cualquiera de las siguientes identidades:

$$\frac{\pi}{4}=\sum_{m=0}^{+\infty}\frac{(-1)^m}{2m+1}\ \ \hspace{4em}\ \ \frac{\pi^2}{6}=\sum_{m=1}^{+\infty}\frac{1}{m^2}.$$

19. Sea $a:N^2\rightarrow N$ una función de apareamiento y sean

$$\mbox{\it car}^a,\mbox{\it cdr}^a:N\rightarrow N$$

sus correspondientes funciones proyecciones. Sea $a^*:N^*\rightarrow N$ la correspondiente enumeración de las sucesiones de naturales de longitud finita. Muestre que las siguientes funciones $N^*\times N^*\rightarrow N$ son computables:

$$\begin{array}{cc} \mbox{\it pre}(\mbox{\bf x},\mbox{\bf y})=... ...0 &\mbox{\rm en otro caso. } \end{array}\right. \end{array}$$

20. Muestre que las siguientes funciones $N\times N^*\rightarrow N^*$ son computables:

$$\begin{array}{rcl} \mbox{\it bor}(n,\mbox{\bf x})&=&\left\{\... ...n$ posiciones de los caracteres en $\mbox{\bf x}$} \end{array}$$

Siguiente: Funciones de apareamiento y Un nivel arriba: Funciones recursivas primitivas Anterior: Función de Ackermann