__McCarthy’s 91-function: an unfortunate paradigm__

McCarthy’s 91-function —see below— is an ingenious and at first sight baffling construction, which deserved all the attention it attracted when it became known. Unfortunately it also acquired the status of “difficult testcase” for any proposed theory or set of proof rules for recursively defined functions. This is unfortunate for two reasons. Firstly, this function can be dealt with —see below— by such thoroughly elementary means that it is doubtful whether it is a very good testcase; secondly, its contortions are of such a nature —see below— that any method of dealing with it shows more of those contortions that of the method that is supposed to be illustrated.

McCarthy’s 91-function is `g`, given by the following recursive definition

g(`x`) = __if__ `x` > 100 ⇒ `x` - 10 ⫾ `x` ≤ 100 ⇒ g(g(`x` + 11)) __fi__

and one is asked to demonstrate that it equals `f`, given by

f(`x`) = __if__ `x` > 101 ⇒ `x` - 10 ⫾ `x` ≤ 101 ⇒ 91 __fi__

Here we go!

g(`x`)

`g`

__if__

`x`> 100 ⇒

`x`- 10 ⫾

`x`≤ 100 ⇒ g(g(

`x`+ 11))

__fi__

__if__

`x`> 101 ⇒

`x`- 10

⫾

`x`= 101 ⇒ 91

⫾

`x`≤ 100 ⇒ g(

__if__

`x`+ 11 > 100 ⇒

`x`+ 11 - 10

⫾

`x`+ 11 ≤ 100 ⇒ g(g(

`x`+ 11 + 11))

__fi__)

__fi__

__if__

`x`> 101 ⇒

`x`- 10

⫾

`x`= 101 ⇒ 91

⫾ 89 <

`x`≤ 100 ⇒ g(

`x`+ 1)

⫾

`x`< 89 ⇒ g

^{3}(

`x`+ 22)

__fi__

__if__

`x`> 101 ⇒

`x`- 10

⫾

`x`= 101 ⇒ 91

⫾ 89 <

`x`≤ 100 ⇒ g(101)

⫾

`x`≤ 89 ⇒ g

^{3}(

`x`+ 22)

__fi__

__if__

`x`> 101 ⇒

`x`- 10

⫾ 89 <

`x`≤ 101 ⇒ 91

⫾

`x`≤ 89 ⇒ g

^{2n + 3}(

`y`) for some

`n`≥ 0 and 89 <

`y`≤ 111

__fi__

`g`once in the last alternative

__if__

`x`> 101 ⇒

`x`- 10

⫾ 89 <

`x`≤ 101 ⇒ 91

⫾

`x`≤ 89 ⇒ g

^{2n + 2}(

`y`) for some

`n`≥ 0 and 91 <

`y`< 101

__fi__

`g`another time in the last alternative

__if__

`x`> 101 ⇒

`x`- 10

⫾ 89 <

`x`≤ 101 ⇒ 91

⫾

`x`≤ 89 ⇒ g

^{2n + 1}(91) for some

`n`≥ 0

__fi__

__if__

`x`> 101 ⇒

`x`- 10

⫾

`x`≤ 101 ⇒ 91

__fi__

`f`

`x`) Q.E.D.

That is all, in a long sequence of minute transformations. It is a winding argument that, of course, can be delivered in 57 varieties, but when you have seen one of them, you have seen them all. The 91-function is, as said, an ingenious construction, but it is an unfortunate paradigm since it leads to demonstrations that are both lengthy and boring.

I hope this is the last technical note in which the 91-function is treated.

Plataanstraat 5 5671 AL NUENEN The Netherlands |
21 December 1983 prof.dr.Edsger W. Dijkstra Burroughs Research Fellow |