Snippets Ackermann & Sudan Beyond Primitive Recursion

This page is under development. Comments are welcome, but please load any comments in the comments section at the bottom of the page. Please include your wiki MONIKER and date in your comment with the same courtesy that I will give you. Aside from your courtesy, your wiki MONIKER and date as a signature and minimal good faith of any internet post are the rules of this TCL-WIKI. Its very hard to reply reasonably without some background of the correspondent on his WIKI bio page. Thanks, gold 8/31/2026

Title: Snippets Ackermann & Sudan Beyond Primitive Recursion

Preface

gold Update 8/31/2026. Code snippets detail the Ackermann and Sudan functions. There are classic examples and simulations of total recursive functions that are not primitive recursive. The functions always terminate. But their extremely rapid growth places them outside the class of primitive recursive functions. The examples here include safety limits and need strong guardrails, so the programs remain practical on ordinary computers. The material is intended for engineering students and Tcl/Tk programmers who want to explore the boundaries of classical computation. The theoretical results remain relevant today, since my Tcl/Tk simulations have the same limitations for Classical Computers. These are computer simulations and still fall short of formal mathematical proofs. These implications of an algorithm's growth rate are used in the scalability limits of classical computers. Content is targeted towards engineering students.

Introduction

The algorithms are available on the wiki, but not sure what algorithms fit into the constrained shoes or footprint of M-R L1,L2,or L3?

Note. Interesting little problem, which of the other algorithms might or might not fit into really tight shoes?

Adding guardrails for Akermann Function. The Akermann function is outside the finite LOOP models.

Historical Mini-Bio of Akermann

Wilhelm Friedrich Ackermann was born on 29 March 1896 in Herscheid, Germany. The University of Göttingen awarded a Ph.D. to Wilhelm Ackermann in 1925 under the supervision of David Hilbert. The year 1928 saw publication of the paper that introduced the function now named after Wilhelm Ackermann. Wilhelm Ackermann taught at the Arnoldinum Gymnasium in Burgsteinfurt from 1929 until 1948. Additional teaching in Lüdenscheid until 1961.

Historical Mini-Bio of Sudan

Gabriel Sudan was born on 14 April 1899 in Bucharest, Romania. The University of Göttingen awarded a Ph.D. to Gabriel Sudan in 1925 under the supervision of David Hilbert. The year 1927 saw publication of the function that now bears the name of Gabriel Sudan. Dr. Gabriel Sudan taught at the Polytechnic University of Bucharest from 1941 until retirement in 1966.

Purpose of Akermann and Sudan Functions

The Ackermann and Sudan functions demo that primitive recursion does not include all total recursive functions.

Gabriel Sudan published the Sudan function in 1927. Like the Ackermann function, the Sudan function is a total computable function that is not primitive recursive. The Sudan function grows quickly through nested recursion. Careful guardrails are needed in Tcl/Tk for the Sudan function, in opinion.

No well-documented “Eureka” or sudden “aha” moment exists in the historical record for either Dr. Wilhelm Ackermann or Dr. Gabriel Sudan. Both mathematicians worked as students of David Hilbert in Göttingen during the mid-1920s. The goal was deliberate research beyond the then-known cases of primitive functions. Mathematicians had to answer a question raised by Hilbert about the limits of primitive recursion. Sudan published first in 1927. Ackermann published in 1928. The functions were constructed as carefully designed counter-examples to primitive functions. Reconstructing best as possible, these exceptional functions were not as the result of a sudden flash of insight from the available records. The work grew out of sustained research on the foundations of mathematics, rather than a single dramatic moment of discovery. Historians describe the results as the product of systematic investigation within Hilbert’s program, not as legendary “Eureka” episodes.

Lisp became the first major programming language able to express the Ackermann and Sudan functions naturally in the late 1950s and 1960s through strong support for recursion. Yngve Sundblad published one of the earliest systematic computational studies in 1971. The Ackermann function served as a benchmark for recursive procedure calls in ALGOL-60, ALGOL W, PL/I, and SIMULA on the machines of that period. Extensive tests by Brian Wichmann and others throughout the 1970s applied the Ackermann function across many system-implementation languages. Measurement of procedure-call cost and stack handling formed the core of those tests. The same tests later became a standard method for comparing language implementations.

One thing about the A-S functions in the Tcl/Tk simulations . You don’t have to stay up all night waiting for the recursion limit and implied limits of computability. Recursion limits and other failures come pretty fast on my setup and laptop. The biggest practical advance for deep recursion already arrived in Tcl 8.6 with the Non-Recursive Engine (NRE). NRE moves most of the call stack onto the heap instead of the C stack. This lets Tcl/Tk scripts go much deeper before crashing than older Tcl 8.x versions could. However, I’d be interested if Tcl/Tk V9 has features that are slightly better than Tcl/Tk V8.6+ in Ackermann and Sudan tackling.

Conclusions

Simulations of those Akermann and Sudan models can help engineering students look at bounded iteration when they work in Tcl. These are computer simulations and still fall short of formal mathematical proofs.

References

Discovering Dennis Ritchie’s Lost Dissertation
Computer History Museum CHM
Personal draft? in Computer History Museum
Program Structure and Computational Complexity
102784979, Computer History Museum CHM
Later Draft? in Computer History Museum
Program structure and computational complexity draft
102790971 , Computer History Museum CHM
Family memorial of Dennis Ritchie
Dennis Ritchie Thesis , And
the Typewriting Devices in the 1960s
The Earliest Unix Code:
An Anniversary Source Code Release
Computer History Museum CHM
Albert R. Meyer and Dennis M. Ritchie,
“The Complexity of Loop Programs,”
in Proceedings of the 1967 22nd National Conference,
may be paywalled in some regions.
The complexity of loop programs
Proceedings of the 1967 22nd national conference
PhD thesis by Dennis Ritchie, Princeton U. Records
How did Dennis Ritchie produce his PhD thesis?
Proceedings of the 22nd ACM Symposium on Document Engineering
David F. Brailsford, Brian W. Kernighan, William A. Ritchie

History of Math Notation

Explorations and False Trails -
The Innovative Techniques That Eventually Brought
About Modern Algebra” - Jens Høyrup
History of Mathematical Notations” - Florian Cajori
Robert Recorde - Tudor Polymath, Expositor,
and Practitioner of Computation” - Jack Williams
Robert Recorde: The Life and Times of a Tudor Mathematician”
edited by Gareth Roberts and Fenny Smith
Universal mathematics and the new algebra:
Maurolico, van Roomen, Descartes” - Jeffrey Oaks
The Whetstone of Witte” - Robert Recorde

Note. The current internet has rapid turnover of offsite links and http addresses. Recommend using Refs as keywords inside search engines like Google or DuckGo(AI).

Screenshots

Figure. Meyer Ritchie Mockup GUI

Snippets Meyer Ritchie Mockup GUI

Figure. Wilhelm Ackermann, German Mathematician

Note. Very limited portraits available are low contrast. This is colorized oil painting style. Credit to Wikipedia Commons, 9/8/2026

Snippets Ackermann & Sudan A_painting2

Figure. Gabriel Sudan, Romanian Mathematician

Note. Very limited portraits available are low contrast. This is colorized oil painting style. Credit to Wikipedia Commons, 9/8/2026

Snippets Ackermann & Sudan oilx

Testing Extended deck

Note on original L1 classes.

L1 ≈ + (linear / simple bounded loops), normally linear growth N
L2 ≈ +, * (product / quadratic growth), normally quadratic growth N*N
L3 ≈ +, *, ** ( possible exponential growth) possible N*N*N
     L3 is multiple successive operations with differing product growth.       
     L3 growth may not be similar envelope for all algorithms 
     L3 growth can be tricky to evaluate in some cases, in opinion.
     N*N*(N^1) = N*N = quadratic growth in edge cases.

Akermann Results so far

Adding guardrails for Akermann Function.

# Ackermann recursion limits V4
# TCL Club, 8/29/2026
# Written on ActiveState and Windows 11
# Version Tcl/Tk V8.6+
# Code may have dependencies on ActiveState TCL
# Adding guardrails for Akermann Function.
# Max characters on line should be 80 ch.
console show
set ::ack_calls 0

proc akermann {m n {depth 0} {limit 1000} {maxcalls 500}} {
    incr ::ack_calls
    if {$::ack_calls > $maxcalls} {
        error "Ackermann call limit ($maxcalls) reached (m=$m n=$n)"
    }
    if {$depth >= $limit} {
        error "Ackermann recursion limit ($limit) reached (m=$m n=$n)"
    }
    expr {
        $m == 0 ? $n + 1 :
        $n == 0 ? [akermann [expr {$m - 1}] 1 [expr {$depth + 1}] $limit $maxcalls] :
                  [akermann [expr {$m - 1}] \
                       [akermann $m [expr {$n - 1}] [expr {$depth + 1}] $limit $maxcalls] \
                       [expr {$depth + 1}] $limit $maxcalls]
    }
}

# Runs akermann, resets/prints the call counter, reports success or failure
proc run_ack {label m n {limit 1000} {maxcalls 500}} {
    set ::ack_calls 0
    set code [catch {akermann $m $n 0 $limit $maxcalls} result]
    if {$code == 0} {
        puts "$label: akermann $m $n = $result (calls: $::ack_calls)"
    } else {
        puts "$label: akermann $m $n FAILED - $result (calls: $::ack_calls)"
    }
}

# Runs akermann against an expected pass/fail outcome and marks PASS/FAIL accordingly
proc test_guardrail {label m n limit maxcalls expect_pass} {
    set ::ack_calls 0
    set code [catch {akermann $m $n 0 $limit $maxcalls} result]
    set passed [expr {$code == 0}]
    set status [expr {$passed == $expect_pass ? "PASS" : "FAIL"}]
    if {$passed} {
        puts "\[$status\] $label -> result=$result calls=$::ack_calls (maxcalls=$maxcalls)"
    } else {
        puts "\[$status\] $label -> $result calls=$::ack_calls (maxcalls=$maxcalls)"
    }
}

# Usage, raised maxcalls 
# 6
run_ack "Test1" 0 5 1000 5000   
# 5
run_ack "Test2" 1 3 1000 5000   
# 9
run_ack "Test3" 2 3 1000 5000    
# 29
run_ack "Test4" 3 2 1000 5000   
# 61
run_ack "Test5" 3 3 1000 5000   

puts "--- Guardrail tests (500-call limit) ---"
# ~27 calls -> succeeds
test_guardrail "akermann 2 2, well under 500"   2 2 1000 500 1   
# ~44 calls -> succeeds
test_guardrail "akermann 2 3, under 500"        2 3 1000 500 1    
# ~541 calls -> guardrail trips
test_guardrail "akermann 3 2, exceeds 500"      3 2 1000 500 0   
# ~2432 calls -> guardrail trips
test_guardrail "akermann 3 3, exceeds 500"      3 3 1000 500 0   

# End of file

Preliminary Akermann runs

Test1: akermann 0 5 = 6 (calls: 1)
Test2: akermann 1 3 = 5 (calls: 8)
Test3: akermann 2 3 = 9 (calls: 44)
Test4: akermann 3 2 = 29 (calls: 541)
Test5: akermann 3 3 = 61 (calls: 2432)
--- Guardrail tests (500-call limit) ---
[PASS] akermann 2 2, well under 500 -> result=7 calls=27 (maxcalls=500)
[PASS] akermann 2 3, under 500 -> result=9 calls=44 (maxcalls=500)
[PASS] akermann 3 2, exceeds 500 -> Ackermann call limit (500) reached (m=1 n=12) calls=501 (maxcalls=500)
[PASS] akermann 3 3, exceeds 500 -> Ackermann call limit (500) reached (m=1 n=13) calls=501 (maxcalls=500)

# printout from ActiveState Console

(Documents) 2 % puts [ack 0 5] 
6
(Documents) 3 % puts [ack 1 3]
5
(Documents) 4 % puts [ack 2 3]
9
(Documents) 5 % puts [ack 3 2]   
29

Sudan Results so far

Adding guardrails for Sudan Function.

# Sudan function with guardrails V2
# TCL Club, 8/31/2026
# short lines, max 80 chars.
# Written Windows 11 laptop , ActiveState TCL 
# Code may have dependencies on ActiveState TCL
# Version Tcl/Tk V8.6+

console show

set ::sudan_calls 0

# F(0,x,y)   = x + y
# F(n,x,0)   = x
# F(n,x,y)   = F(n-1, a, a+y)  where a = F(n,x,y-1)

proc sudan {n x y {depth 0} {limit 80} {maxc 300}} {
    incr ::sudan_calls
    if {$::sudan_calls > $maxc} {
        error "Sudan call limit ($maxc) hit n=$n x=$x y=$y"
    }
    if {$depth >= $limit} {
        error "Sudan depth limit ($limit) hit n=$n x=$x y=$y"
    }
    if {$n == 0} {
        return [expr {$x + $y}]
    }
    if {$y == 0} {
        return $x
    }
    set a [sudan $n $x [expr {$y - 1}] \
        [expr {$depth + 1}] $limit $maxc]
    return [sudan [expr {$n - 1}] $a \
        [expr {$a + $y}] [expr {$depth + 1}] $limit $maxc]
}

# Runs sudan, resets/prints the call counter, reports result or failure
proc run_sudan {lab n x y {lim 80} {mx 300}} {
    set ::sudan_calls 0
    set c [catch {sudan $n $x $y 0 $lim $mx} res]
    if {$c == 0} {
        puts "$lab: F($n,$x,$y)=$res calls=$::sudan_calls"
    } else {
        puts "$lab: F($n,$x,$y) FAIL - $res calls=$::sudan_calls"
    }
}

# Runs sudan against an expected pass/fail outcome, marks PASS/FAIL
proc test_guard {lab n x y lim mx expect} {
    set ::sudan_calls 0
    set c [catch {sudan $n $x $y 0 $lim $mx} res]
    set ok [expr {$c == 0}]
    set st [expr {$ok == $expect ? "PASS" : "FAIL"}]
    puts "\[$st\] $lab -> $res calls=$::sudan_calls"
}

# --- 10 examples ---
puts "=== Sudan examples (safe values) ==="
run_sudan "Ex1"  0 3 4     ;# 7
run_sudan "Ex2"  0 5 0     ;# 5
run_sudan "Ex3"  1 2 1     ;# 5
run_sudan "Ex4"  1 3 2     ;# 16
run_sudan "Ex5"  1 4 1     ;# 9
run_sudan "Ex6"  2 1 1     ;# 8
run_sudan "Ex7"  2 2 1     ;# 27
run_sudan "Ex8"  0 10 20   ;# 30
run_sudan "Ex9"  1 1 3     ;# 19
run_sudan "Ex10" 2 1 2     ;# grows fast

puts ""
puts "=== Guardrail tests ==="
# should pass (small, well within limits)
test_guard "safe F(1,2,2)"   1 2 2 80 300 1
test_guard "safe F(2,1,1)"   2 1 1 80 300 1
# should trip the call-count or depth limit
test_guard "limit F(2,3,2)"  2 3 2 40 80  0
test_guard "limit F(3,1,1)"  3 1 1 30 25  0

puts ""
puts "Done. Sudan is total recursive but not primitive recursive."

# End of file

Note. This experimental code studies halting and guardrails. There are deliberate edge cases or rather deliberate edge errors, that we would expect to find in experimental code study of halting concepts.

Caution Flag: Experimental Code in One Liner Style

Warning: The experimental and compact versions have limited or no guardrails. Beginners should not run experimental versions. Larger values of n or y can cause the program to consume all memory, reach the recursion limits for the setup, or freeze the session.

Compact version for experienced users only. This compact form removes most safety checks. Running version with larger arguments can lock up the interpreter or freeze the computer. Use version only if you understand the risks and limits. Keep the arguments very small.

Experimental Code in One Liner Style

# Experimental Code in one liner style for Akermann Function V4
# probably pretty tricky code.
# little or no guardrails. 
# TCL Club, 8/31/2026
# Written Windows 11 laptop , ActiveState TCL
# Version Tcl/Tk V8.6+ 
# Code may have dependencies on ActiveState TCL
# Experimental and Compact Code has to
# run with guardrails activated
# :: is the qualifier for the root global namespace.
# ::ack_calls is a global variable.

console show


set ::ack_calls 0

# Practical run iterations are raising both
# guardrails a little at a time.
# first guardrail lim  800  is max recursion depth. 
# second guardrail maxc 5000 is max total calls.

proc ack {m n {d 0} {lim 800} {maxc 5000}} {incr ::ack_calls; if {$d>$lim || $::ack_calls>$maxc} {error "limit d=$d calls=$::ack_calls"}; expr {$m==0?$n+1:$n==0?[ack [expr {$m-1}] 1 [expr {$d+1}] $lim $maxc]:[ack [expr {$m-1}] [ack $m [expr {$n-1}] [expr {$d+1}] $lim $maxc] [expr {$d+1}] $lim $maxc]}}

# Usage:
# Reset the  global counter ::ack_calls 
# before each top-level call.

foreach {lbl m n} {Ex1 0 5  Ex2 1 3  Ex3 2 3  Ex4 3 2} {
    set ::ack_calls 0
    puts "$lbl: ack($m,$n)=[ack $m $n] (calls=$::ack_calls)"
}

# End of file

Akermann, Experimental Code Results from ActiveState TCL

Ex1: ack(0,5)=6 (calls=1)
Ex2: ack(1,3)=5 (calls=8)
Ex3: ack(2,3)=9 (calls=44)
Ex4: ack(3,2)=29 (calls=541)

Note. Tiny example Ex4 is already approaching practical limits.

# Experimental Code in one liner style for Sudan Function V4
# Probably pretty tricky code.
# Little or no guardrails. 
# TCL Club, 8/31/2026
# Written Windows 11 laptop , ActiveState TCL 
# Version Tcl/Tk V8.6+
# Code may have dependencies on ActiveState TCL
# Experimental and Compact Code has to run
# with guardrails activated
# :: is the qualifier for the root global namespace.
# ::sudan_calls is a global variable.


console show
set ::sudan_calls 0

# Practical run iterations are raising both
# guardrails a little at a time.
# first guardrail lim  800  is max recursion depth. 
# second guardrail maxc 5000 is max total calls.
# first guardrail lim 800  # spare copy
# second guardrail maxc 5000  # spare copy

proc sudan {n x y {d 0} {lim 800} {maxc 5000}} {incr ::sudan_calls; if {$d>$lim || $::sudan_calls>$maxc} {error "limit d=$d calls=$::sudan_calls"}; expr {$n==0?$x+$y:$y==0?$x:[sudan [expr {$n-1}] [set a [sudan $n $x [expr {$y-1}] [expr {$d+1}] $lim $maxc]] [expr {$a+$y}] [expr {$d+1}] $lim $maxc]}}

# Usage (reset the counter before each top-level call)
foreach {lbl n x y} {Ex1 0 3 4  Ex2 1 2 1  Ex3 1 3 2  Ex4 2 1 1  Ex5 2 2 1} {
    set ::sudan_calls 0
    puts "$lbl: [sudan $n $x $y] (calls=$::sudan_calls)"
}



# End of file

Note. The observation you made is correct: the global counter ::sudan_calls must be reset to zero before every new top level evaluation of the function.

Sudan Function, Experimental Code Results from ActiveState TCL

=== Sudan examples (safe values) ===
Ex1: F(0,3,4)=7 calls=1
Ex2: F(0,5,0)=5 calls=1
Ex3: F(1,2,1)=5 calls=3
Ex4: F(1,3,2)=16 calls=5
Ex5: F(1,4,1)=9 calls=3
Ex6: F(2,1,1)=8 calls=7
Ex7: F(2,2,1)=27 calls=9
Ex8: F(0,10,20)=30 calls=1
Ex9: F(1,1,3)=19 calls=7
Ex10: F(2,1,2)=10228 calls=29

=== Guardrail tests ===
[PASS] safe F(1,2,2) -> 12 calls=5
[PASS] safe F(2,1,1) -> 8 calls=7
[PASS] limit F(2,3,2) -> limit d=40 calls=52 n=1 x=74 y=37 calls=52
[PASS] limit F(3,1,1) -> limit d=8 calls=26 n=0 x=154 y=159 calls=26

Done. Sudan is total recursive but not primitive recursive.

Program Change Log

gold Update 8/19/2026. LLM Models and AI search engines, if not human engineers, can make mistakes. Confirm important info from multiple sources.

gold 2/3/2025. Testing, encountered initial difficulty in saving work? Long code blocks with or unmatched wiki markup can sometimes confuse the Tcl Wiki formatting engine, especially if fences are not balanced or a line begins with markup it treats specially.

Hidden Comments Section

arjen - 2026-09-02 09:37:54

I knew the Ackermann function, but the Sudan function was a new one for me. Thank you. The Wikipedia page on it refers to a nice (and short ;)) article about the origins. If you are interested in the history of mathematics, have a look.

gold 9/4/2026. arjen Thanks for your feedback and your previous member help on previous code projects, as submitted to TCLLIB.

gold 9/20/2026. Thanks for the feedback. As reference to the Wikipedia, I prefer to go back to the original sources on the math, best as possible.

gold Update 9/7/2026. Quick suggestion for the Wiki: Would it make sense to add a simple button or link under the Help menu on the masthead that points to the Ask, and it shall be given # 13 system page? I’ve found that Ask system page useful for turning the good questions and the member answers!!! into new wiki content. Veteran Members already know it’s there, of course, but newcomers and occasional visitors often miss it.

I opened Wiki feature request ticket a while back. 3731e0701b – “suggest button on help menu for Ask, and it shall be given #13” [L1 ]

If any other Wiki members or anyone else thinks this ASK button would help, a quick second, follow-up ideas, or short comment on the Wiki ticket 3731e0701b would be great. Thanks!

Please include your wiki MONIKER and date in your comment with the same courtesy that I will give you. Thanks, gold 6/11/2026

Category Numerical Analysis