Problem 6

The McCarthy 91 function $M:\mathbb{Z}\to\mathbb{Z}$ is a recursive function created by computer scientist John McCarthy to test formal verification in computer science. It is defined as follows.

1. Show $M(101)=91$.

2. Show $M(n)=M(n+1)$ for all $90\leq n\leq 100$.

3. Deduce that $M(n)=91$ for all $90\leq n\leq 100$.

4. Hence prove that $M(n)=91$ for all $n\leq 100$.