m ← ##.m91 n                                ⍝ McCarthy's M91 function.

The McCarthy 91 function  is a recursive function, defined by John McCarthy as a
test case for formal verification within computer science.

http://en.wikipedia.org/wiki/McCarthy_91_function

The recursive definition:

    M n → n-10,       if n>100
    M n → M(M(n+11)), otherwise

is nicely expressed as a dfn:

    m91←{               ⍝ non-tracing version
        ⍵>100: ⍵-10     ⍝ high number: M(n) → n-10
        ∇ ∇ ⍵+11        ⍝ low number:  M(n) → M(M(n+11))
    }

We  can  watch  the progress of the sequence by displaying the value of ⍵ at the
start  of  each  function invocation and passing, as left argument, which of the
recursive calls was used:

    m91←{                       ⍝ McCarthy's M91 function.
        ⍺←'' ⋄ ⍞←⍺,⍕⍵           ⍝ trace:
        ⍵>100:⍵-10              ⍝ high number: M(n) → n-10
        ')'∇'('∇ ⍵+11           ⍝ low number:  M(n) → M(M(n+11))
    }

Then:

    m91 2
2(13(24(35(46(57(68(79(90(101)91(102)92(103)93(104)94(105)95(106)96(107)97(108)9
8(109)99(110)100(111)101)91(102)92(103)93(104)94(105)95(106)96(107)97(108)98(109
)99(110)100(111)101)91(102)92(103)93(104)94(105)95(106)96(107)97(108)98(109)99(1
10)100(111)101)91(102)92(103)93(104)94(105)95(106)96(107)97(108)98(109)99(110)10
0(111)101)91(102)92(103)93(104)94(105)95(106)96(107)97(108)98(109)99(110)100(111
)101)91(102)92(103)93(104)94(105)95(106)96(107)97(108)98(109)99(110)100(111)101)
91(102)92(103)93(104)94(105)95(106)96(107)97(108)98(109)99(110)100(111)101)91(10
2)92(103)93(104)94(105)95(106)96(107)97(108)98(109)99(110)100(111)101)91(102)92(
103)93(104)94(105)95(106)96(107)97(108)98(109)99(110)100(111)101
91

We could generalise the function by parameterising the constants that define the
breakpoint and increments:

    mGen←{              ⍝ McCarthy's M91 function (generalised)
        ⍺←11 100 ¯10    ⍝ default increments and breakpoint
        lo brk hi←⍺     ⍝ increment for hi and low numbers and breakpoint
        {               ⍝
            ⍵>brk:⍵+hi  ⍝ high number: M(n) → n-hi
            ∇ ∇ ⍵+lo    ⍝ low number:  M(n) → M(M(n+lo))
        }⍵
    }

Then:

    5 10 ¯4∘mGen¨ 5 to 15
7 7 7 7 7 7 7 8 9 10 11

    5 10 ¯3∘mGen¨ 5 to 15
8 9 8 9 8 9 8 9 10 11 12

Examples:

    m91¨ 90 to 100                  ⍝ ⍵<100 → 91
91 91 91 91 91 91 91 91 91 91 91

    m91¨ 101 to 110                 ⍝ ⍵≥100 → ⍵-10
91 92 93 94 95 96 97 98 99 100

See also: osc k6174

Back to: contents

Back to: Workspaces