El propósito de este post es demostrarles que la maximización acotada de un predicado recursivo primitivo es recursiva primitiva.
Concretamente, sea \( n\in\mathbb{N} \) y \( P:\mathbb{N}^{n+1}\longrightarrow \{0,1\} \) un predicado recursivo primitivo.
Queremos demostrar que la función \( \text{maxb}_{P}:\mathbb{N}^{n+1}\longrightarrow\mathbb{N} \) definida como
\( \text{maxb}_{P}(\vec{x},t)=\begin{cases}0 & \text{ si }P(\vec{x},y)\text{ es falso para todo }y\leq t\\\max\{y\leq t:P(\vec{x},y)\} &\text{ en caso contrario}\end{cases} \)
es recursiva primitiva
Pues bien, \( \text{maxb}_{P}(\vec{x},0)=0 \) y
\( \text{maxb}_{P}(\vec{x},t+1)=\text{maxb}_{P}(\vec{x},t)\cdot (1-P(\vec{x},t+1))+P(\vec{x},t+1)\cdot (t+1) \)
La razón es la siguiente: si no hay ningun \( y\leq t+1 \) tal que \( P(\vec{x},y) \) es verdadero, entonces ambos miembros de la expresión anterior son iguales a cero. Si por el contrario, existe \( y\leq t+1 \) tal que \( P(\vec{x},y) \) es verdadero, entonces puede ocurrir que el más grande de tales \( y \)'s sea menor o igual que \( t \) (en cuyo caso \( P(\vec{x},t+1)=0 \)), o bien que el más grande de tales \( y \)'s sea igual a \( t+1 \) (en cuyo caso \( P(\vec{x},t+1)=1 \)). A partir de esto, vemos claramente la igualdad de las dos expresiones.
Así, es muy fácil convencerse que \( \text{maxb}_{P}(\vec{x},t+1)=H(\vec{x},t,\text{maxb}_{P}(\vec{x},t)) \) para una función recursiva primitiva \( H \).
