McCarthy 91 Function - Proof

Proof

Here is a proof that the function behaves as expected.

For 90 ≤ n < 101,

M(n) = M(M(n + 11)) = M(n + 11 - 10), where n + 11 >= 101 since n >= 90 = M(n + 1)

So M(n) = 91 for 90 ≤ n < 101.

We can use this as a base case for induction on blocks of 11 numbers, like so:

Assume that M(n) = 91 for a ≤ n < a + 11.

Then, for any n such that a - 11 ≤ n < a,

M(n) = M(M(n + 11)) = M(91), by hypothesis, since a ≤ n + 11 < a + 11 = 91, by the base case.

Now by induction M(n) = 91 for any n in such a block. There are no holes between the blocks, so M(n) = 91 for n < 101. We can also add n = 101 as a special case.

Read more about this topic:  McCarthy 91 Function

Famous quotes containing the word proof:

    “He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
    —Herman Melville (1819–1891)

    “It comes to pass oft that a terrible oath, with a swaggering accent sharply twanged off, gives manhood more approbation than ever proof itself would have earned him.”
    —William Shakespeare (1564–1616)

    “Right and proof are two crutches for everything bent and crooked that limps along.”
    —Franz Grillparzer (1791–1872)