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:

    “O, popular applause! what heart of man
    Is proof against thy sweet, seducing charms?”
    —William Cowper (1731–1800)

    “There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
    —Herman Melville (1819–1891)

    “The insatiable thirst for everything which lies beyond, and which life reveals, is the most living proof of our immortality.”
    —Charles Baudelaire (1821–1867)