Siguiente: Segunda lista de programas Un nivel arriba: Teoría de la recursividad Anterior: Malas noticias: No hay

Tercera lista de ejercicios

En esta lista usaremos las notaciones siguientes

$$\begin{eqnarray*}\left\{f_i\right\}_{i\geq 0} &:&\mbox{\rm\begin{minipage}[t]{25... ...funciones recursivas cuyo dominio es $N^n$ .\end{minipage}} \\ \end{eqnarray*}$$

Dada una clase ${\cal F}^{(n)}$ de funciones $N^n\rightarrow N$, una función universal para ${\cal F}^{(n)}$ es una función $U^{(n)}:N^{1+n}\rightarrow N$ tal que

• Toda sección de U está en la clase ${\cal F}^{(n)}$, i.e.
  
  $$\forall m\in N:\ (\mbox{\bf x}\mapsto U(m,\mbox{\bf x}))=\lambda\mbox{\bf x}(U(m,\mbox{\bf x}))\in{\cal F}^{(n)}.$$
  
  

• Toda función en la clase se ``realiza'' como una sección de U:
  
  $$\forall f\in {\cal F}^{(n)}\exists i_f\in N:\forall \mbox{\bf x}\in N^n\ \ U(i_f,\mbox{\bf x})=f(\mbox{\bf x}).$$
  
  
  En tal caso i_f es un índice de f correspondiente a U.

Sea $a:N^2\rightarrow N$ una función de apareamiento, sea ${\cal F}^{(1)}$ una clase de funciones $N\rightarrow N$ y sea $U^{(1)}:N^2 \rightarrow N$ una función universal para ${\cal F}^{(1)}$. Diremos que ${\cal F}^{(1)}$ contiene a su propia función universal si $U^{(1)}\circ a\in {\cal F}^{(1)}$.




1. Resuelva la ecuación

$$3x\equiv 2\mbox{\rm mod }78.$$

2. Resuelva el sistema de ecuaciones

$$\begin{eqnarray*}x &\equiv& 7\mbox{\rm mod }9 \\ x &\equiv& 13\mbox{\rm mod }23 \\ x &\equiv& 1\mbox{\rm mod }2 \end{eqnarray*}$$

3. Resuelva el sistema de ecuaciones

$$\begin{eqnarray*}2x &\equiv& 3\mbox{\rm mod }5 \\ 4x &\equiv& 3\mbox{\rm mod }7 \end{eqnarray*}$$

4. Construya una función universal para los polinomios de una sola variable con coeficientes en Z, i.e. para la clase Z[x].

5. Muestre que toda familia finita de funciones posee una función universal.

6. Diremos que una función $G:N \rightarrow N$ es general si para cualquier $i\geq 0$ existe una función computable total $g_i:N \rightarrow N$ tal que

$$\forall x:\ G(g_i(x))=f_i^{(1)}(x).$$

a) Muestre que existen funciones generales. Sugerencia: Considere una función universal U⁽¹⁾, la enumeración de Cantor c y sus respectivas proyecciones $\mbox{\it car}$ y $\mbox{\it cdr}$. Considere $G=U\circ(\mbox{\it car},\mbox{\it cdr})$. b) Muestre que existen funciones que no son generales. c) Muestre que existe una infinidad de funciones generales.

7. Sea $c:N^2 \rightarrow N$ la enumeración de Cantor y sea $c^k:N^k \rightarrow N$ su k-ésima iteración:

$$c^k(x,\mbox{\bf x}^{(k-1)})=c(x,c^{k-1}(\mbox{\bf x}^{(k-1)})).$$

a) Bosqueje la construcción de un programa-while que calcule c. Sea m el número de variables en este programa. b) Bosqueje la construcción de un programa-while que calcule c^k utilizando a lo sumo m+k variables.

8. Muestre que la clase de funciones recursivas $N\rightarrow N$ contiene a su propia función universal.

9. Sea ${\cal F}$ la mínima clase de funciones $N\rightarrow N$ que contiene a la función cero y a la diagonal $x\mapsto a(x,x)$, donde a es una función (computable) de apareamiento, y que es cerrada bajo el esquema de composición de funciones. Muestre que ${\cal F}$ no puede contener a ninguna función universal suya. Sugerencia: Revise el Lema de la Diagonal.

10. Muestre que Z[x] no puede contener a ninguna función universal suya.

11. Sea $F:N \rightarrow N$ la función

$$x\mapsto F(x)=\left\{\begin{array}{ll} 1 &\mbox{\rm si $f_x^... ... 0 &\mbox{\rm si $f_x^{(1)}(0)\uparrow$. } \end{array}\right.$$

Muestre que F no puede ser recursiva.

12. Sea $\Theta:N \rightarrow N$ la función

$$x\mapsto \Theta(x)=\left\{\begin{array}{ll} {\displaystyle \... ...$, } \\ \perp &\mbox{\rm en otro caso. } \end{array}\right.$$

Muestre que $\Theta$ sí es recursiva.

13. Decida si acaso la función $F:N \rightarrow N$ tal que

$$x\mapsto F(x)=\left\{\begin{array}{ll} 1 &\mbox{\rm si $f_x^... ...x)=1$, } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$$

es recursiva. Justifique su respuesta.

14. Muestre que la función

$$F(i,j)=\left\{\begin{array}{ll} 1 &\mbox{\rm si $\exists k<j... ...$, } \\ \perp &\mbox{\rm en otro caso. } \end{array}\right.$$

es computable. Sugerencia: Dado (i,j) ``simule'' la corrida en paralelo de los cálculos de los valores $f_i^{(1)}(0),\ldots,f_i^{(1)}(j-1)$, parándose con el valor requerido cuando se pare el primero, en pararse, de esos cálculos.

15. Muestre que la función

$$F(i,j)=\left\{\begin{array}{ll} 1 &\mbox{\rm si $\exists k>j... ...$, } \\ \perp &\mbox{\rm en otro caso. } \end{array}\right.$$

es computable. Sugerencia: Proceda como en el ejercicio anterior recorriendo, digamos que mediante la enumeración de Cantor, a los elementos

$$s_{kl}^{ij}=\mbox{\rm\begin{minipage}[t]{25em} $l$-\'esimo estado al que llega el c\'alculo de $f_i^{(1)}(k)$,\end{minipage}}$$

con k>j , $l\geq 0$.

16. Sean $g,h:N\rightarrow N$ dos funciones computables. Construya una función computable $f:N\rightarrow N$ que satisfaga las siguientes dos condiciones

$$\begin{eqnarray*}\mbox{\rm i)} && \mbox{\rm dom}(f)=\mbox{\rm dom}(g)\cup \mbox{... ... ii)} && \forall x\in\mbox{\rm dom}(f): f(x)=g(x)\lor f(x)=h(x) \end{eqnarray*}$$

17. Muestre que la función

$$F(i)=\left\{\begin{array}{ll} 1 &\mbox{\rm si $f_i^{(1)}\not... ...$, } \\ \perp &\mbox{\rm en otro caso. } \end{array}\right.$$

es computable.

18. Definiremos una nueva enumeración

$$\eta:N\rightarrow \{\mbox{\rm funciones recursivas}\}$$

de las funciones recursivas $N\rightarrow N$ como sigue: Sea $a:N^2\rightarrow N$ una función computable de apareamiento con proyecciones respectivas $\mbox{\it car}^a,\mbox{\it cdr}^a$. Dado $m\in N$, escribamos $m_1=\mbox{\it car}^a(m)$ y $m_2=\mbox{\it cdr}^a(m)$. Entonces $g_m=\eta(m)$ es la función definida por las siguientes dos relaciones:

$$\begin{eqnarray*}g_m(0) &=& \left\{\begin{array}{ll} m_1-1 &\mbox{\rm si $m_1\n... ...rray}\right. \\ \forall x\not=0:\ g_m(x) &=& f_{m_2}^{(1)}(x) \end{eqnarray*}$$

Muestre que la enumeración anterior es biyectiva, es decir

$$\begin{eqnarray*}\forall m,n &:& \eta(m)\equiv \eta(n)\;\Rightarrow\; m=n \\ \forall i\exists m &:& f_{i}^{(1)}\equiv \eta(m) \end{eqnarray*}$$

19. Considere la enumeración $\eta$ del ejercicio anterior. Muestre que existe una función recursiva H tal que

$$\forall m:\ \ \eta(m)\equiv f_{H(m)}.$$

20. Decida si acaso existe una función recursiva G ``inversa'' de la anterior, es decir, tal que

$$\forall i:\ \ f_{i}\equiv \eta(G(i)).$$

Siguiente: Segunda lista de programas Un nivel arriba: Teoría de la recursividad Anterior: Malas noticias: No hay