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)

    “There is no better proof of a man’s being truly good than his desiring to be constantly under the observation of good men.”
    —François, Duc De La Rochefoucauld (1613–1680)

    “If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
    —Thomas Jefferson (1743–1826)