Autor Tema: Maximización acotada

0 Usuarios y 1 Visitante están viendo este tema.

30 Abril, 2020, 01:30 am
Leído 204 veces

numbsoul

  • Nahuel Albarracín
  • Moderador Global
  • Mensajes: 1,848
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
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 \).