Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Sudan function
open-in-new
<p>In the <a href="/facts/Theory_of_computation/xYJd2YeI">theory of computation</a>, the Sudan function is an example of a <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> that is <a href="/facts/Recursion/CxSKxJoW">recursive</a>, but not <a href="/facts/Primitive_recursive_function/4z97gRnl">primitive recursive</a>. This is also true of the better-known <a href="/facts/Ackermann_function/WQNpCWHn">Ackermann function</a>. </p><p>In 1926, <a href="/facts/David_Hilbert/1vhlHn4b">David Hilbert</a> conjectured that every computable function was primitive recursive. This was refuted by <a href="/facts/Gabriel_Sudan/dnNc7b1s">Gabriel Sudan</a> and <a href="/facts/Wilhelm_Ackermann/8bPlUHSE">Wilhelm Ackermann</a> — both his students — using different functions that were published in quick succession: Sudan in 1927, Ackermann in 1928. </p><p>The Sudan function is the earliest published example of a recursive function that is not primitive recursive. </p>