La función McCarthy es la siguiente:
$M\left(n\right)=\left\{n-10\:\:\:\:\:\:if\:n\:>100\:\right\}$
y
$M\left(n\right)=\left\{M\left(M\left(n+11\right)\right)\:\:\:if\:n\:\le 100\:\right\}$
Para cualquier número entero $n\:\le 100$ , $91$ se devuelve. Es una función ordenada. ¿Hay alguna forma de ajustarla para que funcione con otros números (es decir, para cualquier into hasta el límite superior $r$ , $M()$ devuelve $k$ )?
Arreglar algunos $r $ y $k $ como querías, con $k < r $ .
Sea $d = r-k+1$ y luego defina su función como
$$M(n) = \begin{cases} n - d, n > r\\ M(M(n + d + 1)), n \leq r \end{cases} $$
Su función devuelve ahora $k $ para cualquier $n \leq r $
Para demostrar que funciona, puedes utilizar algún tipo de inducción. Empieza por demostrar que $M(r) = k$ . Entonces demuestre que si $r - d \leq n \leq r, M(n) = k $ . Entonces demuestre que si $n < r-d $ , $M(n)$ se simplificará a $M(n_1) $ con $r-d \leq n_1 \leq r $
Increíble. Si no le importa que le pregunte, ¿cómo lo descubrió? ¿O es algo bien sabido sobre las funciones de McCarthy?
@ChrisT no me importa que me lo preguntes :) la verdad es que me costó bastante intuición y conjeturas. Al ver M definido como M(M(n + 11)) señaló la recursividad y el cálculo de M en algunos puntos clave como 101, 100 y 91 me hizo entender que la forma en que funcionaba era: al calcular M(n), si n es inferior a $r $ sólo calcula M de algo más grande. Esto me dio a entender que M(n) acabaría siendo M(101) para cualquier número. Una vez asimilado esto, generalizar fue bastante fácil.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
