Friday, November 18, 2011

McCarthy's 91 Function in Haskell

I've been reading a lot of articles on wikipedia on different topics of the theory of computation today, and I happened across one on the McCarthy 91 function. This function over the natural number is very simple- f(n) = n - 10 if n > 100 and f(n) = M(M(n + 11)) otherwise.

A proof that M(n) = 91 for all 0 >= n > 101 in Haskell is pretty concise:
m n | n > 100 = n - 10 | otherwise = m $ m $ n + 11
all ((91 ==) . m) [0..101]
Which evaluates to true.

2 comments: