Talk:McCarthy 91 function

I just removed the C iterative example. As pointed out in the comments below, it was quite pointless and potentially confusing; it was essentially a translation of the tail-recursive code into a for-loop. Also the description for it was incorrect, naming it a "tail-recursive" implementation (but "non-functional", whatever that means?) although there was no recursion whatsoever. Vegan Velociraptor (talk) 14:22, 23 March 2017 (UTC)

---

The C example really needs to be removed from this article. The whole point of McCarthy's 91 function is exposition for the doubled recursion; there is no point whatsoever in including an iterative implementation, all it could possibly do is confuse. Moe Aboulkheir 05:32, 5 February 2006 (UTC)

---

Why is this interesting? I accept that it is an example of a recursive function, but I don't see why is deserves an article. And why is it restricted to positive integers? --Henrygb 12:30, 10 Aug 2004 (UTC)

It's interesting because it is. Also, because this function is hilarious.

Here's a function that Henrygb might find interesting. It returns 91 for all input, not just positive integers:

D(x) = 91

---

What was McCarthy's original motivation for this function? A simple illustration of recursion? --Bubba73 14:18, 27 May 2005 (UTC)

---

I just had to refactor the awkward Java implementation of McCarthy's function. Java is not suited to functional programming at all. -- Matthias

---

It is true that java is not well suited for showing recursive functions, but it is good to have its implementation because far more people can read java than lisp. It is a good example of recursion.

As for the lisp implementation, I just couldn't resist adding a nice clean lisp implementation of the same function. :) --pi 17:37, 15 July 2005 (UTC)

---

An algorithm does seldom correspondend one-on-one with its implementation in a relatively low level language such as java. We should keep the iterative version in java to show that you sometimes have to obfuscate your ideas to make your computer run them. -- Matthias

---

Shouldn't the M(n-10) in the beginning sentence just say n-10?Blueyoshi321 02:58, 22 November 2005 (UTC)

• I think so, I've changed it back. Nick8325 12:40, 22 November 2005 (UTC)

Why does it say C++, isn't that Java?

int mccarthy(int n) {

   for (int c = 1; c != 0; ) 
   {
       if (n > 100) 
       {
           n = n - 10;
           c--;
       }
       else 
       {
           n = n + 11;
           c++;
       }
   }
   return n;

}

isn't that Java, not C++? 71.141.127.117 06:19, 17 December 2005 (UTC)

• It seems to be valid C++ as well. In fact, unless I'm mistaken it's C99 too (not C89 because c is declared inside the for loop's initialiser). But in Java, it would need to be wrapped in a class to be valid...it would probably be best to call it C, I think. Nick8325 20:19, 17 December 2005 (UTC)

It won't even work any way. It will never escape the for loop without c==0

• It will escape the for loop when c reaches 0. The loop works out M^c(n), where M^c is M repeated c times (for example, M³(n) = M(M(M(n)))):
  It knows that M⁰(n) is n, so it returns n when c==0.
  It works out M^c(n) = M^c-1(M(n)) =
  • M^c-1(n-10) if n > 100 (the if case)
  • M^c-1(M(M(n+11))) = M^c+1(n+11) if n <= 100 (the else case)
  Since it starts with c=1, it will work out M¹(n), which is M(n).
  (I just tested it, by the way, and it does work. But it's a bit of a strange example to have, I think.)
  Nick8325 12:45, 15 November 2006 (UTC)

---

Why have an iterative example when the function should be written recursively? Besides that, I believe the for loop doesn't belong at all. I don't (yet) know lisp, but here is my try at translating it to Visual Basic:

Public Function MC91(n As Integer)
   If n < 1 Then GoTo NegError
   
   If n <= 100 Then
      MC91 = MC91(MC91(n + 11))
   Else
      MC91 = n - 10
   End If
   
   Exit Function
   
NegError:
   Debug.Print "Function only defined for positive values of n"
End Function

P.S. This function is interesting because of the doubled recursion

WallPhone 25 January 2006 (UTC)

Deletion

I am going to propose a deletion for this article in the next days as still no one can explain why this function is important. --Abdull 15:10, 5 March 2006 (UTC)

It's a quite famous example of a recursive function. It's also nested, which is quite unusual - I can only think of the Ackermann function which also does that. It's probably not important, but plenty of people find it interesting, and (for example) MathWorld has an article on it, so why not Wikipedia? Nick8325 16:10, 5 March 2006 (UTC)

Hi Nick. Actually, MathWorld seems to be the only other useful (Google) source on the Internet on this topic, the others just being mostly mirrors of Wikipedia. It would be great to explain why McCarthy should have come up with this function or proof if McCarthy really did, otherwise it seems like a Nihilartikel or in-joke. --Abdull 19:03, 6 March 2006 (UTC)

Searching for McCarthy 91 function -wikipedia seems to clear out a lot of the mirrors, and there are still a fair number of references left. I don't know why he came up with it, but it's definitely real - I'd heard of it before I read about it here. Looking around a bit more, it seems to have appeared in an article called "Properties of programs and partial function logic", published in 1970. It seems to be in a library near me, I might go and look for it... Nick8325 20:14, 6 March 2006 (UTC)

Okay, you did some fine research. Citeseer has an entry for this paper in its database: http://citeseer.ist.psu.edu/context/350306/0 Now I would like to read that paper to find out the intention for the function. :) --Abdull 16:35, 9 March 2006 (UTC)

Right, I went off to the library and read it. It's actually quite a technical paper, on deciding whether evaluating a recursive function will terminate, by turning it into a logical proposition, under two different evaluation orders - sequential (reducing one expression at a time) and parallel (reducing all the different subexpressions at the same time). He just uses the 91 function as an example, and proves that it will terminate with the value 91.

Strangely enough, it references a couple of earlier things that mention the function. There's "The validity problem of the 91-function", by Zohar Manna and Amir Pnueli, which is referenced as the Stanford Artificial Intelligence Project memo 68, and which I can't find, and there's "Formalisation of properties of recursively defined functions", by the same two. An updated version of the second paper is in the Journal of the ACM for 1970, but that references McCarthy's paper itself! (so the update must have added that reference, I suppose)

I didn't think to make a copy of the paper itself. I could go back and do that tomorrow. Nick8325 22:27, 9 March 2006 (UTC)

See this paper for an example in the literature. The authors are considering various approaches to proving recursively functions terminate. For simple recursions the process can be automated, but for 'nested recursions', such as the 91 function, they require user assistance. If I get a chance, I'll reread the paper and add something to the article.--Malcohol 16:58, 30 May 2006 (UTC)

Another reference is this paper, again used an example.--Malcohol 16:21, 20 July 2006 (UTC)

---

The proof, contributed by Nick8325, can be somewhat simplified: the "blocks of 11" are not necessary - the fact that from a you get to a -11 makes this a case of complete induction. On the other hand, I would consider defining n as 101-a and using induction on n so that the induction proceed, as customary, upwards. AmirOnWiki 11:06, 31 October 2007 (UTC)

---

On March 23, 2010, David Eppstein replaced function with recurrence relation, stating "It's more of a recurrence relation than a function (the function itself is trivial)". I changed this to recursive function (linked to the article on recursive programming), since what all the literature concerning this "function" addresses is neither the mathematical function (which is indeed trivial) nor a recurrence relation, but a programming-language object, a recursive function definition. Function definitions are commonly called "functions" by programmers, and even programming theorists. Moreover, the current definition of recurrence relation does not fit this example very well. AmirOnWiki (talk) 14:26, 5 April 2010 (UTC)