Siguiente: Jerarquía de Grzegorczyk Un nivel arriba: Funciones elementales Anterior: Esquema de transformación explícita

Clase de funciones elementales

Esta clase de funciones es bastante amplia y suficiente para el cálculo de la mayoría de las aplicaciones en ingeniería. En la tabla 2.2 presentamos varias clases de funciones. Probaremos que todas ellas coinciden entre sí. Las funciones en cada una de esas clases son llamadas elementales.

 

Table 2.2: Definiciones alternativas de las funciones elementales.

Todos los polinomios, por ejemplo, son funciones elementales. Se sigue de inmediato la siguiente,

Proposición 2.1   La clase ${\cal E}$ de las funciones elementales está incluída en la clase ${\cal FRP}$ de las funciones recursivas primitivas.

Teorema 2.1   Las clases ${\cal F}^1$, ${\cal F}^2$ y ${\cal F}^3$ coinciden con la clase ${\cal E}$ de funciones elementales.

Hay que probar las inclusiones

$${\cal E}\subset {\cal F}^1\subset {\cal F}^2\subset {\cal F}^3\subset {\cal E}.$$

En nuestra presentación no abundaremos en detalles. Presentaremos más bien meras indicaciones de cómo desarrollar esas demostraciones. Para demostrar una inclusión de la forma ${\cal F}\subset {\cal G}$, donde ${\cal F}$ y ${\cal G}$ son dos clases de funciones definidas recursivamente, hay que ver que

• las funciones básicas de ${\cal F}$ están en ${\cal G}$, y
• ${\cal G}$ es cerrado bajo los esquemas de composición de ${\cal F}$, o lo que es lo mismo, que los esquemas de ${\cal F}$ se construyen con los de ${\cal G}$.

Demostración del teorema. Mostremos que se cumple cada una de las inclusiones necesarias.

1.

${\cal E}\subset {\cal F}^1$:

(a)

En cuanto a las funciones básicas de ${\cal E}$, tenemos que la función sucesor y la diferencia acotada están en ${\cal F}^1$ ex definitione. Para ver que la suma está en ${\cal F}^1$ probemos de manera más general, la proposición siguiente: (Producto y suma con exponenciación y MiAc): La suma y el producto usuales de los número naturales se pueden construir mediante la función exponenciación y el esquema de minimización acotada. En efecto, dado que

$$\begin{eqnarray*}a^{b+c} &=& a^{b}a^{c} \\ a^{bc} &=& \left(a^b\right)^c \end{eqnarray*}$$

tenemos

$$\begin{eqnarray*}x\cdot y &=& \mathop{\rm Min}\{z\leq (x+1)^{y+1}\vert 2^z=(2^x)... ...& \mathop{\rm Min}\{z\leq (x+1)\cdot(y+1)\vert 2^z=(2^x)(2^y)\} \end{eqnarray*}$$

(b)

Observemos ahora algunas propiedades de ${\cal F}^1$:

i.

Los conjuntos en ${\cal F}^1$ forman un álgebra de conjuntos: es decir, $\chi_{\emptyset}\in{\cal F}^1$ y si A,B son dos conjuntos tales que $\chi_A,\chi_B\in{\cal F}^1$ entonces $\chi_{A^c},\chi_{A\cap B}\in{\cal F}^1$. En efecto, la función cero, que es $\chi_{\emptyset}$, está en ${\cal F}^1$ pues esta clase es cerrada por transformación explícita. La otra aseveración se sigue de las relaciones

$$\begin{eqnarray*}x=0 &\Leftrightarrow& 0^x=1 \\ (x=0)\land(y=0) &\Leftrightarrow& x^{0^y}=0 \end{eqnarray*}$$

ii.

${\cal F}^1$ es cerrada bajo proyecciones acotadas. Esto se prueba de manera similar a como se vió que las funciones recursivas primitivas son cerradas bajo proyecciones acotadas.

iii.

${\cal F}^1$ es cerrada bajo el esquema de recursión acotada. Debido a que es cerrada por proyecciones acotadas, puede verse que la relación de ser primo y el tomar descomposiciones en primos de un entero dado son procedimientos en ${\cal F}^1$. Por tanto, podemos codificar secuencias por números en ${\cal F}^1$:

$$\mbox{\bf m}=(m_0,\ldots,m_k)\in I\!\!N^*\ \leftrightarrow\ \lceil\mbox{\bf m}\rceil=\prod_{i=0}^k p_i^{m_i}.$$

Con esto se puede ver que, en efecto, ${\cal F}^1$ es cerrada bajo el esquema de recursión acotada.

(c)

En cuanto a las reglas de composición, basta ver que ${\cal F}^1$ es cerrada bajo la sumatoria y el producto acotados. Pero esto es una consecuencia de que ${\cal F}^1$ es cerrada bajo la recursión acotada.

2.

${\cal F}^1\subset {\cal F}^2$:

(a)

En cuanto a las funciones básicas de ${\cal F}^1$, tenemos que la función sucesor y la exponenciación están en ${\cal F}^2$ ex definitione. La función diferencia acotada, así como la suma y el producto, en ${\cal F}^2$ debido a las leyes de exponenciación: a^x+y=a^xa^y, $a^{xy}=\left(a^x\right)^y$.

(b)

${\cal F}^2$ es cerrado bajo el esquema de minimización acotada debido a que este esquema es constructible en ${\cal F}^2$.

3.

${\cal F}^2\subset {\cal F}^3$: Para ver esto, basta mostrar que ${\cal F}^3$ es cerrado bajo el esquema de recursión acotada. Se debe, entonces, demostrar que ${\cal F}^3$ es cerrado bajo el esquema de minimización acotada. Sea $f\in{\cal F}^3$. Consideremos la función $f_1:(\mbox{\bf x},y)\mapsto{\displaystyle \sum_{z=0}^y \left[1\dot{-}f(\mbox{\bf x},z)\right]}$, que está en ${\cal F}^3$. Tenemos que se cumplen las equivalencias lógicas siguientes:

$$\begin{eqnarray*}x\not=0 &\Leftrightarrow& 1\dot{-}x=0, \\ x=0 &\Leftrightarro... ...ll z:\left[0\leq z<a\Rightarrow f(\mbox{\bf x},z)\not=0\right]. \end{eqnarray*}$$

Sea pues $g:(\mbox{\bf x},y)\mapsto \left({\displaystyle \sum_{z=0}^y \left[1\dot{-}f_1(\... ..._{z=0}^y \left[1\dot{-}f_1(\mbox{\bf x},z)\right]}\right)\dot{-}y\right)\right)$. Es evidente que $g\in{\cal F}^3$ y además puede verse que $g=\mbox{\it MiAc}(f)$. Ya que ${\cal F}^3$ es cerrada por minimización acotada, lo es también por recursión acotada.

4.

${\cal F}^3\subset {\cal E}$: Esta inclusión rige ex definitione también.

Siguiente: Jerarquía de Grzegorczyk Un nivel arriba: Funciones elementales Anterior: Esquema de transformación explícita