History
The 91 function was introduced in papers published by Zohar Manna, Amir Pnueli and John McCarthy in 1970. These papers represented early developments towards the application of formal methods to program verification. The 91 function was chosen for having a complex recursion pattern (contrasted with simple patterns, such as defining by means of ). The example was popularized by Manna's book, Mathematical Theory of Computation (1974). As the field of Formal Methods advanced, this example appeared repeatedly in the research literature. In particular, it is viewed as a "challenge problem" for automated program verification.
Often, it is easier to reason about non-recursive computation. As one of the examples used to demonstrate such reasoning, Manna's book includes a non-recursive algorithm that simulates the original (recursive) 91 function. Many of the papers that report an "automated verification" (or termination proof) of the 91 function only handle the non-recursive version.
A formal derivation of the non-recursive version from the recursive one was given in a 1980 article by Mitchell Wand, based on the use of continuations.
Read more about this topic: McCarthy 91 Function
Famous quotes containing the word history:
“History takes time.... History makes memory.”
—Gertrude Stein (1874–1946)
“The view of Jerusalem is the history of the world; it is more, it is the history of earth and of heaven.”
—Benjamin Disraeli (1804–1881)
“What would we not give for some great poem to read now, which would be in harmony with the scenery,—for if men read aright, methinks they would never read anything but poems. No history nor philosophy can supply their place.”
—Henry David Thoreau (1817–1862)