4

The McCarthy Function is the following:

$M\left(n\right)=\left\{n-10\:\:\:\:\:\:if\:n\:>100\:\right\}$

and

$M\left(n\right)=\left\{M\left(M\left(n+11\right)\right)\:\:\:if\:n\:\le 100\:\right\}$

For any integers $n\:\le 100$, $91$ is returned. It's a neat function. Is there a way to adjust it so that it works with other numbers (i.e. for any into up to upper bound $r$, $M()$ returns $k$)?

Chris T
  • 813

1 Answers1

3

Fix some $r $ and $k $ like you wanted, with $k < r $.

Let $d = r-k+1$ and then define your function as

$$M(n) = \begin{cases} n - d, n > r\\ M(M(n + d + 1)), n \leq r \end{cases} $$

Your function now returns $k $ for any $n \leq r $

To prove that works, you can use some type of induction. Start by showing that $M(r) = k$. Then show that if $r - d \leq n \leq r, M(n) = k $. Then show that if $n < r-d $, $M(n)$ will simplify to $M(n_1) $, with $r-d \leq n_1 \leq r $

RGS
  • 9,719
  • Wow - amazing. If you don't mind me asking, how did you figure this out? Or is this well known about McCarthy functions? – Chris T Nov 14 '16 at 00:44
  • @ChrisT i do not mind you asking :) it actually took me a great deal of intuition and guesswork. Seeing M defined as M(M(n + 11)) pointed out the recursion and calculating M at some key points like 101, 100 and 91 made me understand that the way it worked was: when calculating M(n), if n is below $r $, just calculate M of a bigger thing. This hinted me that M(n) would end up to be M(101) for any number. After that sunk in, generalizing was fairly easy. – RGS Nov 14 '16 at 03:44
  • Very cool, this is hugely helpful and impressive – Chris T Nov 14 '16 at 14:28
  • @ChrisT proving the function works is a rather interesting exercise. I challenge you prove it if you have the time and interest. – RGS Nov 14 '16 at 14:32
  • I think I could use structural induction or just regular induction to do so, I'll try it to better understand how it works – Chris T Nov 14 '16 at 14:34
  • @ChrisT induction will be useful here. Start with your specific example and start by proving that $M(n) = 91$ for $90 \le n \le 101$. – RGS Nov 14 '16 at 14:38