Apart from *Ackermann’s function*, there is another function which is *not primitively recursive* – the *Sudan* function. It was one of the first functions having this property to be published in 1927, derived by Romanian mathematician, Gabriel Sudan (1899-1977) [2]. In the mid 1920s, both Sudan and Wilhelm Ackermann were (PhD) students of David Hilbert at the University of Göttingen in Germany, studying the foundations of computation. Sudan was in Germany from 1922-1925, after which he returned to Romania. Both Ackermann and Sudan are credited with discovering recursive functions that are not *primitive recursive*.

While Ackermann’s function is well known, Sudan’s is not. At the same time that Ackermann submitted his paper for publication, Sudan independently submitted his own work. Sudan cited the ideas of Ackermann contained in a paper by Hilbert [4]. Ackermann also cited knowledge of Sudan’s work [3]. However Sudan’s paper remained relatively unknown, in part because of the obscurity of the journal he published it in. Published in 1927 [2], it was not until 1979 that his contribution was presented at a conference by Calude and colleagues [1]. Here is Sudan’s function:

```
S(m,n,0) = m + n
S(m,0,k) = m
S(m,n,k) = S(S(m,n-1,k),S(m,n-1,k)+n,k-1) for n≥1, k≥1
```

Here is the algorithm implemented in C:

```
int sudan(int m, int n, int k)
{
if (k == 0)
return m + n;
else if (n == 0)
return m;
else if (k != 0 && n != 0)
return sudan(sudan(m,n-1,k),sudan(m,n-1,k)+n,k-1);
}
```

The data in Table 1 shows some of the output for various values of **m**, and **n**, when **k**=1.

n/m | 0 | 1 | 2 | 3 | 4 | 5 | 6 |

0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |

1 | 1 | 3 | 5 | 7 | 9 | 11 | 13 |

2 | 4 | 8 | 12 | 16 | 20 | 24 | 28 |

3 | 11 | 19 | 27 | 35 | 43 | 51 | 59 |

4 | 26 | 42 | 58 | 74 | 90 | 106 | 122 |

5 | 57 | 89 | 121 | 153 | 185 | 217 | 249 |

6 | 120 | 184 | 248 | 312 | 376 | 440 | 504 |

*Some values for m, and n when k=1*

Ackermann cited Sudan’s work in a footnote [3, p.119]:

Original:Eine Arbeit, die mit der vorliegenden manche Berührungspunkte hat, wird von Herrn G. Sudan publiziert werdem. Es handelt sich bei ihr um die Definition von Zahlen der zweiten Zahlklasse, die man in ähnlicher Weise klassifizieren kann wie die Definitionen der reellen Zahlen.

Translation:A work that has some points of contact with the present one will be published by Mr. G. Sudan. It is about the definition of numbers of the second number class, which can be classified in a similar way to the definitions of real numbers.

- Calude, C., Marcus, S., Tevy, I., “The first example of a recursive function which is not primitive recursive”,
*Historia**Mathematica*, 6, pp.380-384 (1979). - Sudan, G., “Sur le nombre transfini ω
^{ω}“,*Bulletin Mathématique de la Société Roumaine des Sciences*, 30, pp.11-30 (1927). - Ackermann, W., “Zum Hilbertschen Aufbau der reellen Zahlen”,
*Mathematische Annalen*, 99, pp.118-133 (1928). - Hilbert, D., “Sur l’infini”,
*Acta Mathematica*, 48, pp.910-922 (1926).